SPOJ - BITMAP (Getting TLE)

general
, ,
1

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.

2

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
3

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:

4

AC… thanks a lot :slight_smile:

1 Like
5

@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…

6

How can we do it with recursion??