C - 器物損壊!高橋君 Editorial by maspy
「\(2\) 回以下壁を壊して到達できるか」という問題ですが,次のように言い換えられます.
- 壁に侵入しない移動:コスト \(0\) かかる.
- 壁に侵入する移動:コスト \(1\) かかる.
- 総コスト \(2\) 以下で到達できるか判定せよ.
各マスに対して,そこに到達するまでの最小コストを求めることができればよいです.これは基本的な最短経路問題で,\(O(HW)\) 時間で解くことができます.(「最短経路問題」「01-BFS」などが検索ワードになると思います.)
posted:
last update: