2026-10-03
Frontier.hs
import Data.List (nub)
maze :: [String]
maze = [ "..#"
, "#.."
, "..." ]
open :: (Int, Int) -> Bool
open (r, c) = r >= 0 && r < 3 && c >= 0 && c < 3 && maze !! r !! c == '.'
step :: [(Int, Int)] -> [(Int, Int)]
step ps = nub [ q | (r, c) <- ps
, q <- [(r + 1, c), (r - 1, c), (r, c + 1), (r, c - 1)]
, open q ]
main :: IO ()
main = print (length (takeWhile (notElem (2, 0)) (iterate step [(0, 0)])))
これは何を出力するでしょうか?
Answer
4 です。
iterate step [(0, 0)] は、[(0, 0)]、それに step を1回適用したもの、2回適用したもの、と続く無限リストです。step は前線のどのマスからも上下左右の通れるマスへ1歩ずつ進めるので、k 番目の要素は、スタートからちょうど k 歩でいられるマスの集まりです。リストは無限でも、takeWhile は条件が初めて偽になった要素で止まり、その先は評価されません。
length が数えるのは、(2, 0) を含まない前線が先頭から何個続くかです。この数は (2, 0) を初めて含む前線の番号と等しく、その番号はゴールにちょうど着ける最小の歩数、すなわち最短距離です。
訪問済みのマスを記録していないので、前線には一度通ったマスへ戻る道も混ざります。それでも答えは変わりません。戻り道は前線に余計なマスを足すだけで、(2, 0) が初めて現れる番号を早めも遅らせもしないからです。訪問済みが無ければ正しく数えられない、と考えるとここで迷います。
迷路では (1, 0) が壁なので、スタートから真下へは進めません。(0, 0)、(0, 1)、(1, 1)、(2, 1)、(2, 0) と回り込む4歩が最短で、ゴールを含まない前線は0番から3番までの4個です。