2026-10-03
Path.hs
type Pos = (Int, Int)
path :: [(Pos, Pos)] -> Pos -> [Pos]
幅優先探索は、スタート以外の各マスについて、そのマスへ初めて来たときの1つ前のマス(親)を記録します。(マス, 親) の組のリストとゴールを受け取り、スタートからゴールまでのマスを順に並べたリストを返す path を書いてください。スタートは親の記録が無いマスです。ゴールがスタートそのものなら、そのマス1つだけのリストを返します。
入力例 1
path [((0, 1), (0, 0)), ((1, 1), (0, 1)), ((1, 0), (0, 0))] (1, 1)
出力例 1
[(0,0),(0,1),(1,1)]
入力例 2
path [((0, 1), (0, 0)), ((1, 1), (0, 1)), ((1, 0), (0, 0))] (1, 0)
出力例 2
[(0,0),(1,0)]
入力例 3
path [] (2, 2)
出力例 3
[(2,2)]
Reference
type Pos = (Int, Int)
path :: [(Pos, Pos)] -> Pos -> [Pos]
path parents = reverse . go
where
go p = p : maybe [] go (lookup p parents)
ゴールから親をたどると、マスはゴール、その親、さらにその親、とスタートへ向かう順に並びます。参考実装の go はこの順にリストを作り、lookup が親を見つけられないマス、つまり親の記録が無いスタートに着いたところで止まります。求めるのはスタートからの経路なので、最後に reverse で向きを逆にします。
maybe [] go (lookup p parents) は、親が見つかれば go でその先をたどり、Nothing なら空リストで終える、という場合分けを1つの式で書いたものです。ゴールがスタートなら lookup は最初から Nothing を返すので、結果はゴール1マスだけのリストになります。
掲載したのは参考実装で、唯一の正解ではありません。case で Just と Nothing を分けて書いても、たどったマスを引数のリストの先頭に積んでいき、reverse を使わずに済ませてもかまいません。