Rubyで理解する蟻本「2−1再起関数 迷路の最短路」

10 10
#S######.#
......#..#
.#.##.##.#
.#........
##.##.####
....#....#
.#######.#
....#.....
.####.###.
....#...G#

# 探索が必要な地点を表すクラス
class Point
  attr_accessor :x, :y
  def initialize(x, y)
    @x = x
    @y = y
  end
end

# 十分に大きい数字
INF = 100_000_000

# 入力内容の読み込み
n, m = gets.chomp.split(" ").map(&:to_i)
# スタートとゴールの場所を初期化
start = Point.new(nil, nil)
goal = Point.new(nil, nil)

maze = []
# 読み込みと同時にスタートとゴールの場所を記憶する
n.times do |index|
  row = gets.chomp
  if row.include?("S")
    start.x = index
    start.y = row.index("S")
  end

  if row.include?("G")
    goal.x = index
    goal.y = row.index("G")
  end
  maze.push(row.split(""))
end

# これから探索する地点を管理するキュー
queue = Array.new

# 4方向のベクトル
delta_x = [1, 0, -1, 0]
delta_y = [0, 1, 0, -1]

# 各点までの最短距離の配列をINFで初期化する
distanse_table = Array.new(n) { Array.new(m, INF) }
# スタートの地点の距離を0にセットする
distanse_table[start.x][start.y] = 0

# キューにスタートの地点を入れる
queue.push(start)

while !queue.empty?
  # キューの先頭を取得する
  current_point = queue.shift

  # 探索がゴールに来たらループから抜ける
  break if current_point.x == goal.x && current_point.y == goal.y

  # 移動できる場所それぞれについて、距離計算未済かつ壁じゃないことを確認して、自分のいる場所+1をセットする
  4.times do |index|
    # 確認するポイントの座標
    checking_x = current_point.x + delta_x[index]
    checking_y = current_point.y + delta_y[index]
    # 迷宮の中にいる、かつ計算未済、かつ壁じゃない
    if 0 <= checking_x && checking_x < n &&
        0 <= checking_y && checking_y < m &&
        distanse_table[checking_x][checking_y] == INF &&
        maze[checking_x][checking_y] != "#"
      # 自分のいる場所 + 1
      distanse_table[checking_x][checking_y] = distanse_table[current_point.x][current_point.y] + 1
      # その地点をキューに入れる
      queue.push(Point.new(checking_x, checking_y))
    end
  end
end

# 答え
puts distanse_table[goal.x][goal.y]

## 00 ## ## ## ## ## ## 13 ##
02 01 02 03 04 05 ## 13 12 ##
03 ## 03 ## ## 06 ## ## 11 ##
04 ## 04 05 06 07 08 09 10 11
## ## 05 ## ## 08 ## ## ## ##
08 07 06 07 ## 09 10 11 12 ##
09 ## ## ## ## ## ## ## 13 ##
10 11 12 13 ## 17 16 15 14 15
11 ## ## ## ## 18 ## ## ## 16
12 13 14 15 ## 19 20 21 22 ##