解法
マス目を移動する際のコストを辺とみなしながらダイクストラ法を用いていくとよいです。
遷移の種類はいくつかあり、
コスト
で、塀でない上下左右の隣接したマスに移動する
コスト
で、上下左右の隣接したマスに移動する
コスト
で、右上、右下、左上、左下の斜めのマスに移動する
です。
もちろん、下の2つの遷移を行うには、今いるマスを含めて周囲9マスのどこにも爆弾が存在しない、という条件が必要です。
しかし、斜めに移動する遷移を先に行っておくことにより、どの塀がまだ存在しているか、という情報を持つ必要はなくなります。
あとは、これをもとにしてダイクストラ法を用いることによって、答えを求めることができます。
感想
ダイクストラ法で、priority_queueにプッシュする要素は、最短コストを更新(もしくは初めて来た)場合なのですが、現状の最短コストと等しい場合にもプッシュをしてしまうと、ほぼほぼTLEします。
ということを過去何回もやってきたのですが、今回もやらかしました。悲しいです。
