Submission #691667

---

Source Code Expand

R, C = gets.chomp.split("\s").map(&:to_i)
s_y, s_x = gets.chomp.split("\s").map(&:to_i)
g_y, g_x = gets.chomp.split("\s").map(&:to_i)

maze = [Array.new(C + 2, "#")]
maze += R.times.map { ["#"] + gets.chomp.split("") + ["#"] }
maze += [Array.new(C + 2, "#")]

steps = Array.new(R + 2).map { Array.new(C + 2, -1) }

queue = []
queue.push([s_y, s_x])

until queue.empty?
  y, x = queue.shift
  coordinates = [[y - 1, x], [y + 1, x], [y, x - 1], [y, x + 1]]
  candidates = coordinates.map { |t_y, t_x| steps[t_y][t_x] }
  steps[y][x] = (candidates.reject { |e| e == -1 }.min || -1) + 1

  queue +=
    coordinates.reject do |t_y, t_x|
      maze[t_y][t_x] == "#" || steps[t_y][t_x] != -1
    end
  queue = queue.uniq
end

puts steps[g_y][g_x]

Submission Info

Judge Result