Please subscribe to the official Codeforces channel in Telegram via the link https://t.me/codeforces_official. ×

vishudon's blog

By vishudon, history, 2 months ago, In English

Hello,

I am solving below problem and I have already solved this problem using DFS, but then I tried to solve it using BFS too. I know that below problem can be solved using both BFS and DFS.

I have written a solution using BFS, but my solution is failing at #19 test case (not complete visible test case). I tried hard to debug my code, but can't understand where is the problem in my code. I checked many BFS solutions for this problem, but none of the solution could help me resolving issue in my code. Can someone please help me with this ? Any help will be appreciated. Thanks in advance.

Problem Link: https://codeforces.com/contest/510/problem/B

My Solution Link: https://codeforces.com/contest/510/submission/124016916 ( This solution is failing at #19 test case)

 
 
 
 
  • Vote: I like it
  • -16
  • Vote: I do not like it

»
2 months ago, # |
  Vote: I like it +8 Vote: I do not like it
  • »
    »
    2 months ago, # ^ |
      Vote: I like it +6 Vote: I do not like it

    Thank you so much for fixing, but can you please suggest a test case where my solution fails ? it will really be helpful. Thanks again !

  • »
    »
    2 months ago, # ^ |
    Rev. 4   Vote: I like it +16 Vote: I do not like it

    your BFS code may got no issue on the idea. but when you verify that an neighbor of current cell is distinct to its parent, you just need to check if the rows OR columns of both cells are distinct or not. since you write (new_i!=p_i) && (new_j!=p_j), it means the new cell and parent cell are both distinct at their rows AND columns.