AOJ 0558 Cheese

gistfile1.fs

let [| height; width; cheeseSize |] = System.Console.ReadLine().Split([|' '|]) |> Array.map int
let maze = 
  [| for x = 0 to height - 1 do
       yield System.Console.ReadLine().ToCharArray() |] 

let start = ref (0, 0)

for h = 0 to height - 1 do
  for w = 0 to width - 1 do
    if maze.[h].[w] = 'S' then
      start := (h, w)

let rec bfs s d power =
  let queue = System.Collections.Generic.Queue<int*int>()
  queue.Enqueue(s)
  let distance = Array2D.init height width (fun x y -> if (x, y) = s then d else System.Int32.MaxValue)
  let goal = ref (0, 0)
  while queue.Count <> 0 do
    let (h, w) = queue.Dequeue()
    for (dh, dw) in [ (-1, 0); (0, -1); (1, 0); (0, 1) ] do
      if h+dh >= 0 && w+dw >= 0 && h+dh < height && w+dw < width && maze.[h+dh].[w+dw] <> 'X' &&
         distance.[h+dh, w+dw] = System.Int32.MaxValue then
        distance.[h+dh, w+dw] <- distance.[h, w] + 1
        if '0' <= maze.[h+dh].[w+dw] && maze.[h+dh].[w+dw] <= '9' && int(maze.[h+dh].[w+dw])-int('0') = power then
          goal := (h+dh, w+dw)
        else
          queue.Enqueue(h+dh, w+dw)
  if power < cheeseSize then
    bfs !goal (distance.[fst !goal, snd !goal]) (power+1)
  else 
    distance.[fst !goal, snd !goal]

let answer = bfs !start 0 1

printfn "%A" answer