Namaran

Code daily. Without assist.

2026-10-03

Maze.hs

type Pos = (Int, Int)

maze :: [String]
maze = ["...", ".#.", "..."]

open :: Pos -> Bool
open (r, c) = r >= 0 && r < 3 && c >= 0 && c < 3 && maze !! r !! c == '.'

bfs :: Pos -> [(Pos, Int)] -> [Pos] -> Maybe Int
bfs _ [] _ = Nothing
bfs goal ((p@(r, c), d) : rest) seen
  | p == goal = Just d
  | otherwise = bfs goal (next ++ rest) (map fst next ++ seen)
  where
    next = [ (q, d + 1) | q <- [(r + 1, c), (r, c + 1), (r - 1, c), (r, c - 1)]
                        , open q, q `notElem` seen ]

main :: IO ()
main = print (bfs (0, 2) [((0, 0), 0)] [(0, 0)])

bfs は、迷路 maze のマス (行, 列) を上下左右に1歩ずつ進み、スタートからゴールまでの最短の歩数を返す関数です。引数も標準入力も使わず、(0, 0) から (0, 2) までの歩数を出力します。いまは Just 6 が出力されます。本来の出力は Just 2 です。

Answer

Wrong

| otherwise = bfs goal (next ++ rest) (map fst next ++ seen)

next ++ rest は、新しく見つけたマスをリストの先頭に置きます。次に取り出されるのは今いるマスの隣なので、待ち行列のつもりのリストが、後から入れたものを先に出すスタックとして働き、探索は深さ優先になります。

(0, 0) の隣は下の (1, 0)、右の (0, 1) の順に見つかり、先頭の (1, 0) が先に調べられます。そこから (2, 0)、(2, 1)、(2, 2)、(1, 2) と壁を回り込み、6歩目で (0, 2) に着きます。(0, 1) は1歩目でリストに入ったのに、後ろに残されたままです。深さ優先では、ゴールに最初に着いた道が最短とは限りません。

Right

| otherwise = bfs goal (rest ++ next) (map fst next ++ seen)

新しいマスを末尾に足せば、リストは先に入れたものから出す待ち行列になります。歩数 d のマスをすべて取り出し終えるまで歩数 d + 1 のマスは出てこないので、ゴールを初めて取り出したときの歩数が最短です。この迷路では (0, 1) から (0, 2) へ進み、Just 2 になります1。

  1. rest ++ next は rest の長さに比例する時間がかかります。大きな迷路では、両端への追加が償却定数時間で済む Data.Sequence を使うのが普通です。これは containers パッケージのモジュールで、Haskell 2010 の標準ライブラリには含まれません。