CSES Graph Algorithms Monsters

Revision en1, by Gagandeep98, 2020-06-05 21:32:34

It is becoming very common that I am failing some of the test cases of CSES problems. I am getting WA on 3 out of 17 test cases. I am unable to figure out what is wrong in my approach.

Logic:

Step 1: Apply BFS for all monsters. Store in dist array, dist[i][j], shortest time among all monsters to reach, coordinate (i, j).

Step 2: Apply BFS for A. Store in d array, shortest time from A to coordinate (i, j). It is only possible to reach that coordinate if d[i][j] < dist[i][j]. Check if we have reached the border.

Step 3: Backtrack to generate the path.

PROBLEM LINK CODE LINK

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en1 English Gagandeep98 2020-06-05 21:32:34 696 Initial revision (published)