朝日新聞2004年5月29日のパズルパーク問題

問題

以下のような街並みがある。白い部分が道路である。が泥棒,が行き止まり,が脱出成功とする。

1分で泥棒は交差点を1つ移動できる。泥棒が移動したら行き止まりを1つ追加できる。

泥棒は逃げ出すことが出来る。その経路と時間を示せ。

ちなみに交差点が灰色に見えるのは「ヘルマン(ハーマン)格子(Hermann Grid)」と言う。

解答への道(ヒント)

今回は何となくコンピュータで解けそうな問題だと思いきや...

手で簡単に解けてしまうんだな。プログラム好きには悲しい問題だ。

泥棒が逃げ出せるのは以下の図のように逃げ場が2箇所ある地点へ到達した場合だけ。それ以外は逃げ場に近い交差点を塞がれたらお終い。

ということで,上記地点に泥棒が移動するにはどうしたら良いか考える。泥棒が以下のように移動し直ぐに脱出出来ない状況を作ると逃げ場が2箇所の地点を塞がれてしまうのでダメ。

そこで泥棒は常に脱出できる状況を連続して作りながら逃げ場が2箇所の地点まで到達しなければならない。

こうすると次に逃げられてしまうので,唯一の逃げ場を塞ぐ。

これを繰り返して左上の地点に到達する。