Problem 82

Dijkstraで解く。
先と同様。

import Dijkstra
import Data.Graph
import Data.Array.IArray

w = 80
xi (i,j) = w*i+j

mkGraph = buildG (0,w*w+1).(s++).(t++).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)],inRange b x]
          s = [(w*w,k*w)|k<-[0..w-1]]
          t = [((k+1)*w-1,w*w+1)|k<-[0..w-1]]
mkWeight a = array ((0,0),(w*w+1,w*w+1)) .(s++).(t++).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)],inRange b x]
          s = [((w*w,k*w),a!(k,0))|k<-[0..w-1]]
          t = [(((k+1)*w-1,w*w+1),0)|k<-[0..w-1]]
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