ABC 151 D - Maze Master のコーナーケース

グラフが与えられて、最も離れている点同士を求めるような問題の場合、

「どこでもいいのでテキトウな点から一回BFSして、最も距離遠い点Aを見つけ、点Aから再度BFSをして最も遠い点Bを見つける」

という二重BFSをやると、最も離れている点のペア(A,B)を見つけられる。

…と思っていたが、

”迷路上の最も離れている地点同士を求める”という問題である、このABC151 Dでこれをやると、WAになる。

例えば、スタートする"テキトウな点"を、左上から順に見て最初に壁ではなかった点にする場合、ケース【hand_04】だけがWA。

公式解説も、スタートする点を全探索するような方法をとっている。

手元で迷路をいくつも書いて、やってみる。全例通るんだけど？

何で【hand_04】だけ二重BFSでは通らないのか？

やっと見つけた”コーナーケース”は、

こんな迷路。

二重BFSをやってみる。

緑色の点を”テキトウな”スタート地点とした場合、こんな感じ。

最大距離は「6」にみえるが…？

真の解は、このパターン。

最大距離は「8」。

…ということで、この問題は、二重BFSでは通りません。

とりあえず「木」なら、二重BFSでよいけど…、ということのかな？

閉路がある場合は、ダメっぽいのかな（嘘解法で通るときもありそう？）。