(V 1.5.5) 19.4 Compute enclosed regions solution is incorrect?

#1

inside the while loop of MarkRegionIfSurrounded(…), once you check if a point is W and border, you are not doing BFS of the remaining nodes adjacent to it

Consider this example where you code wont work
B B B B
W W B B
B B B B
B B B B

in this above case, when you call the API for (1,0), it will figure its a boundary (keep it as is) and leave the function without processing the remaining nodes. So, the next time, when it comes for 1,1 , it will mark it as B even though a route exists to the boundary from 1,0 (As the if check fails and for loop inside else will not add 1,0 to the queue given its already visited)

In my opinion, one correct way is to have a bool that tells if we discovered a W close to boundary anytime during BFS. However, we keep continuing BFS until we exhaust all adjacent W and mark them visited (and eventually leave them as is)
In the event we don’t find a boundary, for all the Ws in the queue, we just turn them B. Makes sense?

Let me know if I am missing something

0 Likes
#2

Hey @aselkapa,

I tried to run the program but did not find any problem of this case. For this problem, those two ‘W’ should not change according to problem definition. One easy way to tell is to run the program and let it output the result. Please try that, and let me know. You can always download the latest program in our repository.

0 Likes
#3

In python code I was confused in the last line.

board[:] = [[‘B’ if c!=‘T’ else ‘W’ for c in row] for row in board]

will set all nodes

  • which are not T to B.
  • which are T to B.
    So it sets the enclosing white nodes to B.
  1. But, what about the nodes which are already are B, won’t it set them to W as well.
  2. Another doubt, what is the need [:]? Wouldn’t it be the same without it?
0 Likes