||For the BFS example, 1000 from Division 1 in SRM 156
There seems to be a simpler (and faster?) solution here:
Step 1, suppose only one player can move (say X moves, Y doesn’t), find the shortest path (from X to Y) using BFS;
Step 2, now let X & Y both move from each end of the shortest path. when they become neighbour, X & Y do a swap and move further along the path.