when trying to update from (ux,uy) to (vx,vy)  i was checking if (vx,vy) was already popped from priority_queue.

this got me wa 22 many times. later, just out of frustation i removed the check and let (vx,vy) be updated even after it was once popped. and u know what, mysteriously got AC. of course, there has to be some logical explanation behind that.

please explain anyone?

Thanks in advance.

I followed by your advice, and also suprised!

Consider this test

4 5
1 1
4 5
11111
22221
21111
22222

You may get caught by situation that '2' at (3,1) gets way longer walking path from '1' at (3,2) than from '2' at (2,1). I remedied this by traversing both fronts in parallel, so it's still O(N*M) BFS w/o heaps or sorting.

Edited by author 23.06.2026 21:29