日々精進

新しく学んだことを書き留めていきます

プログラミングコンテストチャレンジブック演習「迷路の最短路」

今回のお題はこちら。

ゴール地点の最短経路の長さのみ答えればいいんですが、デバッグのために探索済みの範囲の最短経路も表示するようにしてます。
今回は多次元配列の初期化方法を↓のブログで新しく学びました。
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