Блог пользователя vishudon

Автор vishudon, история, 3 года назад, По-английски

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://mirror.codeforces.com/contest/510/problem/B

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

  • Проголосовать: нравится
  • -16
  • Проголосовать: не нравится

»
3 года назад, # |
  Проголосовать: нравится +8 Проголосовать: не нравится
  • »
    »
    3 года назад, # ^ |
      Проголосовать: нравится +6 Проголосовать: не нравится

    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 !

  • »
    »
    3 года назад, # ^ |
    Rev. 4   Проголосовать: нравится +16 Проголосовать: не нравится

    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.