迷路の最短路

dungeon.rb

## 迷路の最短路
## http://rubyfiddle.com/riddles/d4bdf

$field = []

INF=100000
start = []
$goal = []
ans = INF

#迷路
data = <<"EOS"
*S******.*
......*..*
.*.**.**.*
.*........
**.**.****
....*....*
.*******.*
....*.....
.****.***.
....*...G*
EOS

data = data.split("\n")

M=data.size

M.times{|i|
  $field[i] = data[i].split("")
}

N=$field[0].size

def btf(i,j)
  route = []
  # 左、下、右、上
  dx=[1, 0, -1, 0]
  dy=[0, 1, 0, -1]
  d = Array.new(10).map!{Array.new(10,INF)}
  route << [i,j]
  d[i][j] = 0

  while route.size > 0
    p = route.pop
    if p == $goal
      break
    end
    4.times{|m|
      nx = p[0] + dx[m]
      ny = p[1] + dy[m]
      if (0<=nx && nx<N && 0<=ny && ny<M && $field[nx][ny] != "*" && d[nx][ny]== INF)
        route << [nx,ny]
        d[nx][ny]=d[p[0]][p[1]]+1
      end
    }
  end
  return  d[$goal[0]][$goal[1]]
end

N.times{|i|
 M.times{|j| 
   if $field[i][j] == "S"
     start = [i,j] 
   elsif $field[i][j] == "G"
     $goal = [i,j]
     break
   end
 }
}
ans = btf(start[0],start[1]) 

if ans !=  INF
  puts ans
else
  puts ""
end