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.
update the size of dist and d matrix to 1001 as the constraints are n<=1000 and m<=1000.
Since you have done this problem can you let me know why is the answer for this test case NO
4 4
hash hash hash hash
dot dot A hash
hash dot hash hash
hash M hash hash
My code gives the answer as:
YES
2
LL
Update: I got it... I was looking at wrong output.
Can anyone help me why I am getting TLE for the below code. https://cses.fi/paste/48434fbc6c787d57222ddb/
Changed lines 82 and 88. As you were initializing
ans = path[x][y] + ans
, you were actually creating theans
string every time you reinitialized it (which caused the TLE as itO(len ^ 2)
). But if you do it with the help of shorthand methodans += path[x][y]
and then reverse it finally, the compiler optimizes toO(len)
in total and hence we can avoid TLE;