# AtCoder Beginner Contest 151

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

# D

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

max = 0
(1..h).each do |sy|
  (1..w).each do |sx|
    next if arr[sy][sx] == "#"
    # deep copy
    maze = Marshal.load(Marshal.dump(arr))

    # 座標, 回数
    bfs = [[sy, sx, 0]]
    maze[sy][sx] = "#"

    # bfs
    result = nil
    while bfs.length > 0 do
      y, x, result = bfs.shift
      [[-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
    max = result if result > max
  end
end

puts max
Last Updated: 2020/08/15 20:23