Haskellで蟻本やるぜ3（迷路の最短路）

前回の続き。
2-1の迷路の最短路をやるぜ。
今日のパクリもとも前回と同じ、ここだ。

-- 迷路の最短路
-- https://lvs7k.github.io/posts/2018/11/pccb-easy-1/
import Data.Array.Unboxed (UArray)
import Data.Array.IArray
import qualified Data.Set as S

solve :: Int -> Int -> [String] -> Int
-- dropWhileでqueueからgoalが出てくるまで取り出す
solve n m xss = fst . head $ dropWhile ((/= goal) . snd) queue
  where
    -- startの位置 (x,y)=(2,1) ※1始まり fstに位置、sndにcharデータが入る
    (start, _) = head . filter ((== 'S') . snd)
               $ zip [(i, j) | i <- [1 .. n], j <- [1 .. m]] (concat xss)
    -- goalの位置 (x,y)=(9,10) ※1始まり
    (goal, _)  = head . filter ((== 'G') . snd)
               $ zip [(i, j) | i <- [1 .. n], j <- [1 .. m]] (concat xss)
    -- 地図データ
    maze = listArray ((1, 1), (n, m)) (concat xss) :: UArray (Int, Int) Char
    -- リスト(queueで余再帰) 「:」でつなげていく
    -- queueの中身(手数, 位置)
    -- 開始位置をData.Setに変換(S.singleton start)して、goにわたす
    queue = (0, start) : go (S.singleton start) queue
    -- 探索 sは、既に探索済みの位置情報（Data.set型）
    go s ((dist, (i, j)):qs) = next' ++ go s' qs
      where
        -- 4方向を探索する
        next  = filter f2 $ filter f1 [(i - 1, j), (i + 1, j), (i, j - 1), (i, j + 1)]
        -- 移動できる位置集合と手数(dist)を返す
        next' = [(dist + 1, p) | p <- next]
        -- 探索の開始位置をData.Setに放り込む
        s' = foldr S.insert s next
        -- その方向に移動可能か
        f1 pos
            | inRange ((1, 1), (n, m)) pos
                , (maze ! pos) `elem` ['.', 'G'] = True
            | otherwise                          = False
        -- 既にその場所を訪れたか
        f2 = (`S.notMember` s)

rInt :: String -> Int
rInt str = read str :: Int

main :: IO ()
main = do 
    n <- rInt <$> getLine
    m <- rInt <$> getLine
    inp <- getContents
    let maps = lines inp
    -- print maps
    print $ solve n m maps

data.txt

10
10
#S######.#
......#..#
.#.##.##.#
.#........
##.##.####
....#....#
.#######.#
....#.....
.####.###.
....#...G#

実行するぜ。

$ stack runghc main.hs < data.txt
22

解けたぜ。
いやー、start/goal位置や地図データ取る辺りまでは簡単なんだけど、
キューを作って探索してそれに突っ込んでいくところがなかなかイメージできなかったのう。
特にgoのパラメータのsは何だ？というのがわかるまで、ちょっと時間がかかったぜ。