今回のお題はこちら。
ゴール地点の最短経路の長さのみ答えればいいんですが、デバッグのために探索済みの範囲の最短経路も表示するようにしてます。
今回は多次元配列の初期化方法を↓のブログで新しく学びました。
http://d.hatena.ne.jp/octech/20051014
こんな感じで一行ですべての要素を初期化できるのはいいですね。
$distance = Array.new( N ).map!{ Array.new( M, INF ) }
require 'pp' $maze = [ ["#", ".", ".", ".", "#", ".", ".", ".", ".", "."] \ ,["S", ".", "#", "#", "#", ".", "#", ".", "#", "."] \ ,["#", ".", ".", ".", ".", ".", "#", ".", "#", "."] \ ,["#", ".", "#", ".", "#", ".", "#", ".", "#", "."] \ ,["#", ".", "#", ".", "#", "#", "#", "#", "#", "#"] \ ,["#", ".", ".", ".", ".", ".", "#", ".", ".", "."] \ ,["#", "#", "#", ".", "#", ".", "#", ".", "#", "."] \ ,["#", ".", "#", ".", "#", ".", "#", ".", "#", "."] \ ,[".", ".", ".", ".", "#", ".", ".", ".", "#", "G"] \ ,["#", "#", "#", ".", "#", "#", "#", ".", ".", "#"] \ ] #input Sx = 1 #input スタート地点の座標。上記mazeの見た目とx,yが逆になっているので注意。 Sy = 0 #input Gx = 8 #input ゴール地点の座標 Gy = 9 #input N = $maze.length M = $maze[0].length MoveVectors = [[1, 0], [0, -1], [-1, 0], [0, 1]] INF = 2**29 $distance = Array.new( N ).map!{ Array.new( M, INF ) } def bfs() que = Array.new que.push({:x => Sx, :y => Sy}) $distance[Sx][Sy] = 0 while(que.size) p = que.shift MoveVectors.each do |vector| x = p[:x] + vector[0] y = p[:y] + vector[1] if 0 <= x && x < N && 0 <= y && y < M if $maze[x][y] == "G" $distance[x][y] = $distance[p[:x]][p[:y]] + 1 return true elsif $maze[x][y] == "." && $distance[x][y] == INF $distance[x][y] = $distance[p[:x]][p[:y]] + 1 que.push({:x => x, :y => y}) end end end end return false end def infToSharp() for i in 0..($distance.length - 1) for j in 0..($distance[0].length - 1) $distance[i][j] = "#" if $distance[i][j] == INF end end end bfs() infToSharp() pp $distance