BFS で解くことを考えます。BFS をするグラフをグラフ \(G\) として、\(G\) の頂点数と辺数はどれほどでしょうか。

頂点数について、スケート場のマス目の数は \(O(HW)\) と非常に多いため、マス目全てを \(G\) の頂点とすることはできません。
一方、高橋君が停止する可能性のあるマス目の数は少なく、\(O(N)\) しかありません。
なぜなら、停止しうるのは各障害物に隣接する \(4\) マス(とスタートマス)しかないからです。
よって \(G\) の頂点を、高橋くんが停止しうるマス, スタートマス, ゴールマスだけに限定することによって、頂点数を \(O(N)\) とすることができます。

辺数について、\(G\) の全ての頂点について、出次数は高々 \(4\) です。
なぜなら、高橋君の行動パターンは上下左右のどれを選ぶかの \(4\) 通りしかないからです。
よって、\(G\) の辺数も \(O(N)\) としてよいです。

以上より、頂点と辺を全て列挙して BFS をすることでこの問題を解くことができました。