SPOJ - BITMAP (Getting TLE)

I was trying this problem on spoj - http://www.spoj.com/problems/BITMAP

I am pushing all the white cells on a queue, and performing a BFS. The soultion times out. Here is my code - http://ideone.com/kJDx68

Please see if anyone can help me with this.

Thanks in advance.

There are lots of mistake you are doing… Try finding them…!!

Your solution will give WA at the first place …
See this : http://ideone.com/Ph6fog

Now regarding the TLE … There are lots of unnecessary iterations you are doing in the BFS function… You need to fix this … Your code will run out of time for some Worst cases…
See this : http://ideone.com/JMF44l

2 Likes

@rsaha77
for input
2 2
01
01
your code answer is
1 0
2 0
but the correct answer is
1 0
1 0
This is because ur pushing the nodes into queue first and then while u r poping the elements from queue then ur updating the grid array value .
in above example at begining the elements in queue are {(1,2),(2,2)}
now ur poping (1,2) and the nodes connected to it are (1,1) and (2,2).u will only push (1,2) (with z value 0+1) into queue and not (2,2) because (2,2) is having grid value 0.after that u are poping (2,2) from grid and the nodes connected to it are (1,2)and(2,1) u will push (1,2) only into queue (with z value 0+1) into queue.
Now ur queue is {(1,2)(with z value 1) and(2,1)(with z value 1)}
now u will pop (1,2) and the node connected to it with grid value -1 are (2,1)
so now ur pushing (2,1)(with z value 1+1).
now ur queue is having values {(2,1)(with z value 1) and(2,1)(with z value 2)}
finally u are ended with grid[2][1]=2
so this the error…

How can we do it with recursion??

I got one of the mistake, i was doing. I should update the grid array while pushing the point onto the queue. I did that, and the number of iterations reduced drastically, from 740000 to 400 in your test case. But, i still get WA. Thanks, for the testcases.:slight_smile:

AC… thanks a lot :slight_smile:

1 Like