TPC追いコン-A 不完全迷路
一日溶かした
問題概要
スタートとゴールそれぞれのマスを含んだ迷路が与えられる
入力例5
7 8 .#...... S#.#.### ...#.#.# ###.#.G. .....#.. ..##.#.# ........
入力のままだとSからGには到達できない
一つの#を.に変えることでSからGに到達が可能になる最短経路のうち、最大のものを答えよ
考察・解法
何を言ってるんだ…？ 最短経路のうち最大…？？！？！？？！？
とりあえず最短経路なのでBFSだ
全ての
#を.に変えたときを一つずつ見ていき、SからGの最短経路を求める
→ TLE (H, W <= 298でほぼ毎時BFSを行なったらヤバい)SとGからそれぞれBFSし、お互いの領域から
#を一つ挟んでいる箇所を探す
→ 半分WA (???????????)
長考の末、落ちるケースを発見した
以下の入力の場合を考えます
5 5 S.... .##.# ##.#. ..... #.#.G
BFSで求めた各マスの最短経路は以下の様になる
以下では縦軸をx, 横軸をyとする
x = 2, y = 3の#を外す場合を考える (図の赤丸)
このときx = 2, y = 2 (赤丸の左)に移動すればSからGまでの経路は最大になるが、最短経路にはならない
ここさえ注意できればすぐできると思う
