This problem can be solved with a 01-BFS (Breadth-First Search).

Assuming that he does not punch until needed, we can assume that a \(2 \times 2\) region of destroying blocks is adjacent to the square Takahashi is at.

When Takahashi is in the square labeled \(T\) in the diagram below, after a single punch he can move to any square labeled *, regardless of the previous state of the squares.

.***.
*****
**T**
*****
.***.

Therefore, we can assume that a move on foot to an adjacent square costs \(0\) and moving to any * square after a punch costs \(1\), and perform a 01-BFS to solve the problem. The computational complexity is \(O(HW)\).

Similar problem: ABC176D “Wizard in Maze”