Contest Duration: - (local time) (100 minutes) Back to Home
Official

## E - Stronger Takahashi Editorial by en_translator

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”

posted:
last update: