AtCoder Regular Contest #005 C.器物破損！高橋君

その他

問題

WxHのグリッドが与えられる。
各点について、スタート地点、ゴール地点、移動できる場所、壁の情報が与えられる。
上下左右に移動でき、スタート地点から2回まで隣接する壁を壊して移動できる場合、ゴール地点にたどり着くことができるかどうかを答える。

考え方

スタート地点から幅優先探索で移動できるところを探す。
移動できるところに隣接している壁をリストアップ。その壁の上下左右で移動できるマスにしるしをつけておく。
もししるしがついているマスが壁がない場所だった場合はまた幅優先探索する。
幅優先探索してリストアップされていない壁としるしがついている壁についてリストアップ。その壁の上下左右で移動できるマスにしるしをつけておいて、しるしがついているマスが壁じゃなければ幅優先探索する。
これらの間にゴール地点にたどり着けていればYES。そうでなければNO。

周るマスは500*500だけなので、時間は大丈夫。

反省

「上下左右に対して、移動コストが0か1のエッジを持つグラフとみなせ、幅優先探索でコストが2以下で移動できる点について確認」