Consider solving this problem with BFS (Breadth-First Search). Let \(G\) be the graph we perform BFS on. How many vertices and edges does \(G\) have?

Let’s consider the vertices first. Since the number of squares in the skating rink is \(O(HW)\), which is too many to represent all the squares as the vertices of \(G\).
On the other hand, the number of squares at which Takahashi may stop is as small as \(O(N)\), because he may stop only at the four adjacent squares to each obstacle (and the staring square).
Therefore, by confining the vertices of \(G\) to the squares Takahashi may stop, the starting square, and the ending square, the number of vertices can be reduced to \(O(N)\).

Let’s consider the edges next. For every vertex in \(G\), the number of outgoing edges is at most \(4\).
This is because Takahashi’s move is limited to the four directions, up, down, left, or right.
Therefore, the number of edges can be confined to \(O(N)\) too.

Hence, the problem has been solved by enumerating all the vertices and edges, and performing BFS on it.