i_love_math's blog

TLE in SPOJ problem BITMAP
By i_love_math, history, 9 years ago, In English

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

  • Vote: I like it
  • 0
  • Vote: I do not like it

»
9 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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.

→ Reply
  • »
    »
    9 years ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

    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.

    → Reply
    • »
      »
      »
      9 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      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.

      → Reply
      • »
        »
        »
        »
        9 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        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.

        → Reply