Project Euler 解答

Project Euler Problem 083

Project Euler Problem 083

import Data.Graph.Inductive import Data.Graph.Inductive.Graph as G import System.IO.Unsafe import Data.List import Data.Array type GG = Gr Integer Integer -- 入力の二次元配列 ss = map (\x -> read ("["++x++"]")::[Integer]) $ lines $ unsafePerformIO $ readFile "083matrix.txt" n = length ss -- 縦 m = length $ head ss -- 横 -- 入力を配列に変換した sa = listArray ((0,0),(n-1,m-1)) $ concat ss l=[-1,0,1] way4=[(a,b)|a<-l,b<-l,abs(a+b)==1] -- [(-1,0),(0,-1),(0,1),(1,0)] -- 1D 2D変換 ds x y = x*n+y sd v = (v`quot`n,v`rem`n) -- 辺のつながりリスト es ar= [ (ds x y,ds a b,ar!(a,b)) | -- 本問でのコストは移動先のノードの値 (x,y)<-indices ar, (u,v)<-way4, let (a,b)=(x+u,y+v), inRange (bounds ar) (a,b)] -- ノードのリスト ns ar = [(ds x y,sa!i)|i@(x,y)<-indices sa] -- グラフの作成 grh :: GG grh = mkGraph (ns sa) (es sa) -- 最短経路のノード番号 shortest = sp (ds 0 0) (ds (n-1) (m-1)) grh -- 最短経路の値 shortestval = map (\x -> sa!(sd x)) shortest ans = sum shortestval -- 425185 main = print ans

since 2013