Problem 83
Dijkstraで解く。
前と全く同じ。
むしろ、補助頂点の数が少ないので楽とも。
import Dijkstra import Data.Graph import Data.Array.IArray w = 80 xi (i,j) = w*i+j mkGraph = buildG (0,w*w).((w*w,0):).concatMap e$range b where b = ((0,0),(w-1,w-1)) e (i,j) = [(xi (i,j),xi x)|x<-[(i-1,j),(i+1,j),(i,j+1),(i,j-1)],inRange b x] mkWeight a = array ((0,0),(w*w,w*w)) .(s:).concatMap e $range b::Weight where b = ((0,0),(w-1,w-1)) e (i,j) = [((xi (i,j),xi x),a!x)|x<-[(i-1,j),(i+1,j),(i,j+1),(i,j-1)],inRange b x] s = ((w*w,0),a!(0,0)) mkArray ::String->Array (Int,Int) Int mkArray ws= listArray ((0,0),(w-1,w-1)) ws' where ws'=concat.map (read.g).lines$ws g x = "["++x++"]" main =do f<-readFile "matrix.txt" print.fst.shortestPath mkGraph (mkWeight$mkArray f) (w*w) $w*w-1