Problem 83

Dijkstraで解く。

前と全く同じ。

むしろ、補助頂点の数が少ないので楽とも。

import Dijkstra
import Data.Graph
import Data.Array.IArray
w = 80
xi (i,j) = w*i+j
mkGraph = buildG (,w*w).((w*w,):).concatMap e$range b
where b = ((,),(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 ((,),(w*w,w*w)) .(s:).concatMap e $range b::Weight
where b = ((,),(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,),a!(,))
mkArray ::String->Array (Int,Int) Int
mkArray ws= listArray ((,),(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