Let \(d(i, j)\) be the minimum number of moves Takahashi must take before reaching a goal, which may be \(\infty\) if it’s impossible. Obviously \(d(i, j) = 0\) if \((i, j)\) is a goal cell. Otherwise, it’ll be \(1\) plus the second-minimum \(d(x, y)\) among neighboring cells \((x, y)\), because Aoki will prevent traveling to the neighbor with the minimum cost.

There are thus at least two possible methods, both being a modification of a regular multi-source BFS:

• Whenever you dequeue a vertex and check its neighbors, check that the original vertex has the second-minimum cost among the neighbor’s neighbors before updating that neighbor
• (Better constant factor) The first time you discover a cell via one of its neighbors, you merely mark it without updating its cost or enqueueing. Only update its cost (and enqueue if the cost is reduced) if a marked cell is discovered again from another neighbor.

This solves the problem in \(O(HW)\), which should be fast enough.