http://projecteuler.net/index.php?section=problems&id=81
http://projecteuler.net/index.php?section=problems&id=82
http://projecteuler.net/index.php?section=problems&id=83
3題とも同じアルゴリズムで計算できる。違うのは初期のマスと最小を取るマス。Problem 82は初期は左1列で、右1列の最小を取る。
import Data.Map (fromList, lookup, insert, (!)) import Data.List (sortBy) split [] = [[]] split (c:cs) | c == ',' = []:(split cs) | otherwise = (c:s):ss where s:ss = split cs matrix :: [Char] -> [[Int]] matrix s = map (map read) (map split (lines s)) dirs = [ (1, 0), (0, 1), (0, -1), (-1, 0) ] solve mat k = if k /= 82 then m!(n,n) else foldl1 min [ m!(n,y) | y <- [1..n] ] where (m, ps) = update (fromList (init k)) (init k) a = fromList (zip [(x,y) | y <- [1..n], x <- [1..n] ] (concat mat)) n = length mat dir = take (k - 79) dirs init k = if k /= 82 then [((1,1),a!(1,1))] else sortBy (\a b -> compare (snd a) (snd b)) [ ((1,y),a!(1,y)) | y <- [1..n] ] update m [] = (m,[]) update m (p:ps) = update m1 ps1 where (m1, ps1) = f m (map (step (fst p)) dir) ps (m!(fst p)) f m [] ps v0 = (m, ps) f m (pt:pts) ps v0 | is_OB pt = f m pts ps v0 | otherwise = case Data.Map.lookup pt m of Just v1 -> f m pts ps v0 Nothing -> f (insert pt v m) pts (ins [] ps (pt,v)) v0 where v = v0 + (a!pt) ins q1 [] (pt,v) = q1 ++ [(pt,v)] ins q1 (q:q2) (pt,v) | v < snd q = q1 ++ ((pt,v):q:q2) | otherwise = ins (q1 ++ [q]) q2 (pt,v) step (x,y) (dx,dy) = (x + dx, y + dy) is_OB (x,y) = x < 1 || n < x || y < 1 || n < y main = do cs <- readFile "matrix.txt" print (map (solve (matrix cs)) [81..83])