What's special in test 7 ? I tried all the tests given here and I get right answer.

My algorithm is to use bfs to calculate shortest path from source to each destination. If destination is reachable, source is updated to destination else source remains same.
Anything wrong with my method ?

may be some problems with precision?

I got the same problem .. i have WA7 ..
I used BFs .. O(n*m*k) with 2 quest .. one for the blocks whose were reached by vertical or orizontal moves ( last move ) and another for those who were reached with diagonal moves (last move counts only again .. )

with this i do not need to use Heap :( but i got a problem .. i triend almoast every test .. and they worked .. but still WA7 .. :(

my prog. it's not written so well ... so i will not post it .. if you think that it will help you .. ask for it : )

i will keep in touch with this thread :-S

I tried it this way - i.e. propagate all with 1, then with sqrt(2) from current frontier to upcoming edges, but here is the thing:

distance 0 leads to 1 and 1.4 (all still fine and sorted)
distance 1 leads to 2 and 2.4 (all still fine and sorted)
distance 1.4 leads to 2.4 and 2.8 (all still fine and sorted)
distance 2 leads to 3 and 3.4 (all still fine and sorted)
distance 2.4 leads to 3.4 and 3.8 (all still fine and sorted)
distance 2.8 leads to 3.0 and 4.2 (WOOPS! - 3.0 will be placed after 3.4 and 3.8)

so I did  Dijkstra, but with super-optimization. Instead keeping all nodes in a heap, I kept a heap on unique distances (as of A+B*sqrt(2)), and for each such distance I kept bidirectional list of nodes with that distance as currently reached. This makes edge relaxation O(1) - remove from current list, and add to another. So it's O(N*M)+O(K*log(K)) where K is number of different distances, and there are not so much on the way. Although I checked with asserts, there are cases when you have like 8 or even 16 upcoming frontiers even during first 6 tests. Relexations start happening with test 5, but only test 7 leads to WA on them with too greedy approach.

Edited by author 24.06.2026 11:43