フカシギの通行止め(2012.9.16の過去問)

1日1個 @nabetani さんの作った問題を解くAdventCalendarの9日目です。

今日の問題は http://qiita.com/Nabetani/items/9c514267214d3917edf2 にあります。

module Doukaku.Hukashigi (solve) where
import Data.Char (ord)
import Data.List.Split (splitOn)
import qualified Data.Set as Set

type Pt = (Int, Int)

areaSize :: Int
areaSize = 5

solve :: String -> String
solve input = show $ walk areaSize stop (0, 0) Set.empty
  where
    stop = parse input

parseChar :: Char -> Pt
parseChar = flipTupple . flip divMod areaSize . (subtract $ ord 'a') . ord
  where
    flipTupple (x, y) = (y, x)

parse :: String -> Set.Set (Pt, Pt)
parse input = Set.fromList . map parse' $ stops
  where stops = filter (not . null) . splitOn " " $ input
        parse' (x:y:_) = (parseChar x, parseChar y)

isStop :: Set.Set (Pt, Pt) -> Pt -> Pt -> Bool
isStop stop p1 p2 = Set.member (p1, p2) stop || Set.member (p2, p1) stop

walk :: Int -> Set.Set (Pt, Pt) -> Pt -> Set.Set Pt -> Int
walk size stop current@(x, y) done
  | current == (size - 1, size - 1) = 1
  | x < 0 || x >= size || y < 0 || y >= size = 0
  | otherwise = walk' (x, y - 1) + walk' (x, y + 1)
                + walk' (x - 1, y) + walk' (x + 1, y)
  where
    done' = Set.insert (x, y) done
    walk' pt' = if pt' `Set.member` done || isStop stop current pt'
                then 0
                else walk size stop pt' done'

この問題にはsimpath( https://github.com/hiratara/p5-Simpath )という大変効率のよいアルゴリズムが存在しているのですが、今回は素朴な探索で解いています。行き止まりとすでに行った頂点の管理にData.Setを使っています。

問題ページに他の方の回答もありますので、見ると参考になるでしょう。