ACM国際大学対抗プログラミングコンテスト(D)
{-
http://www.acm-japan.org/past-icpc/domestic2006/contest/all_ja.html#section_D
2007.06.12
nisikawa
-}
import Data.Maybe (fromJust)
import Data.List (find, zipWith5)
import Data.Map
type P = (Int, Int)
type M = Map (Int, Int) Int
exec xs = let m = toM xs
p = fst $ fromJust $ find (\(x, y) -> y == 2) $ toAscList m
num = length (f 10 (Just (p, m)))
in if num > 10 then -1 else num
where toM xs = fromList [((x, y), xs !! y !! x) | y <- [0..(length xs) - 1], x <- [0..(length (xs !! y)) - 1]]
vl = pred $ length xs
hl = pred $ length (xs !! 0)
up (x,y) m n = f (n - 1) $ if y == 0 then Nothing else if m ! (x, pred y) == 1 then Nothing else Just $ moveV pred 0 (x, y) m
down (x,y) m n = f (n - 1) $ if y == vl then Nothing else if m ! (x, succ y) == 1 then Nothing else Just $ moveV succ vl (x, y) m
left (x,y) m n = f (n - 1) $ if x == 0 then Nothing else if m ! (pred x, y) == 1 then Nothing else Just $ moveH pred 0 (x, y) m
right (x,y) m n = f (n - 1) $ if x == hl then Nothing else if m ! (succ x, y) == 1 then Nothing else Just $ moveH succ hl (x, y) m
f _ Nothing = [0..]
f n (Just (p,m)) | m ! p == 3 = []
| otherwise = n:zipWith5 g [1..n] (up p m n) (down p m n) (left p m n) (right p m n)
g x _ _ _ _ = x
moveV :: (Int -> Int) -> Int -> P -> M -> (P, M)
moveV f n (x,y) m | y == n = ((x,y), m)
| otherwise = case m ! (x, f y) of
1 -> ((x, y), insert (x, f y) 0 m)
_ -> moveV f n (x, f y) m
moveH :: (Int -> Int) -> Int -> P -> M -> (P, M)
moveH f n (x,y) m | x == n = ((x, y), m)
| otherwise = case m ! (f x, y) of
1 -> ((x, y), insert (f x, y) 0 m)
_ -> moveH f n (f x, y) mちなみに問題(C)は解けませんでしたorz
