# AtCoder Beginner Contest 088

URL: https://atcoder.jp/contests/abc088 (opens new window)

# D

h,w = gets.chomp.split(" ").map(&:to_i)
maze = ["#" * (w + 2)] + h.times.map{"#" + gets.chomp + "#"} + ["#" * (w + 2)]

dot_count = maze.map{|arr| arr.count(".")}.sum

sy, sx = 1, 1
gy, gx = h, w
# 座標, 回数
bfs = [[sy, sx, 0]]
maze[sy][sx] = "#"

# bfs
y, x, result = nil # 最短経路
while bfs.length > 0 do
  y, x, result = bfs.shift
  break if y == gy && x == gx
  [[-1, 0], [1, 0], [0, 1], [0, -1]].each do |(dy, dx)|
    tmp_y = y + dy
    tmp_x = x + dx
    next if maze[tmp_y][tmp_x] == "#"
    maze[tmp_y][tmp_x] = "#"
    bfs << [tmp_y, tmp_x, result + 1]
  end
end

if y == gy && x == gx
  # スタートのdotも対象から外すため
  puts (dot_count - 1) - result
else
  puts -1
end
Last Updated: 2020/08/15 20:23