Блог пользователя i_love_math

TLE in SPOJ problem BITMAP
Автор i_love_math, история, 9 лет назад, По-английски

i am trying to solve http://www.spoj.com/problems/BITMAP/ problem.

my code is giving TLE on SPOJ .

i am not getting why it's getting TLE.

i approached in this procedure: I stored those pixels which have value 1 in a queue and applied bfs across these,

my code is http://ideone.com/ppgQiW

please help

thanks

  • Проголосовать: нравится
  • 0
  • Проголосовать: не нравится

»
9 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

If I understood your code right you do multiple BFS's and all of them pass by all the vertices. That results in a high complexity since there may be up to n*m BFS's, each of them executed in O(n*m).

Try to solve it with only one "complex" BFS that may pass by each vertex more than once, in case a better value for it is found.

This is the code I used: Don't click me . If you still need help message me.

This problem is beautiful, I highly recommend everyone learning basic graph algorithms to solve it.

→ Ответить
  • »
    »
    9 лет назад, # ^ |
      Проголосовать: нравится +3 Проголосовать: не нравится

    You can add all white pixels to the BFS queue at the beginning, then the BFS will find all required distances visiting each vertex only once.

    → Ответить
    • »
      »
      »
      9 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      I have done exacltly that i.e running bfs across those points which are white, but I am getting TLE. Please have a look at my code probably you will understand why I am getting TLE.

      → Ответить
      • »
        »
        »
        »
        9 лет назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится

        You start a new BFS from each white pixel. There's no point in adding a lot of vertices to the BFS at the beginning if then you're gonna create a new queue and a new visited array everytime you pop an element from the queue.

        You have to add all white pixels to the queue and then use that very same queue to do the BFS only once.

        → Ответить