2
2

More than 5 years have passed since last update.

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

Posted at

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を使っています。

2
2
0

Register as a new user and use Qiita more conveniently

1. You get articles that match your needs
2. You can efficiently read back useful information
3. You can use dark theme
What you can do with signing up
2
2