Since we want to decrease the number of move B as few as possible, the basic strategy will be as follows:

• Move to the position that is movable by Move A, then if it is not possible to reach the goal, use Move B to move the place which is not reachable by Move A

With the idea described above in mind, we can see that the grid divides into the region depending on the required number of times to use Move B, which is like, the region where \(0\) times of Move B is required, \(1\) times of Move B is required,… and so on.

To implement this, it is easy to use Breadth-First Search(BFS). Hereinafter, “cost” denotes the number of uses of Move B.

First, start a BFS from the initial square and enumerate the square that can be newly reached to by cost \(0\). Then, from the square that can be reached by cost \(0\), enumerate the square that can be reached by move B that cannot be reached by cost less than or equal to \(0\). Next, starting from the squares that can be reached by cost \(1\), which was found by the steps above, enumerate all the square that can be reached by cost \(1\) using BFS. By repeating this, for all reachable square, you can find the cost required to reach there.

Also, when the cost of a move is either \(0\) or \(1\), an implementation called 01-BFS is possible. Prepare a deque, push the vertices that can be moved to with cost \(0\) to the front of the deque, and push the vertices that can be moved to with cost \(1\) to the back of the deque, and you can perform searching in the order of distances.

Note that, if a vertex which was added via cost \(1\) is later added only via cost \(0\), the same vertex will be added twice, so be careful of the implementation.

The time complexity is \(O(HW)\) since only the move of \(25\) squares are examined.

Sample Code (TODO)