def pp(c) c.each do |l| puts l end puts end $dx = [0,1,0,-1] $dy = [1,0,-1,0] $m = Array.new $mm = Array.new w, h = gets.split.map(&:to_i) c = h.times.map{gets.chomp} bl = false c.each_with_index do |line,i| line.each_char.with_index do |cc,j| next unless cc == "." q = [[i,j]] while q.size > 0 sy, sx = q.shift c[sy][sx] = "a" $m.push([sy,sx]) for i in 0..3 cy = sy + $dy[i] cx = sx + $dx[i] if c[cy][cx]=="." && cy.between?(0,h-1) && cx.between?(0,w-1) q.push([cy,cx]) end end end bl = true break end break if bl end bl = false c.each_with_index do |line,i| line.each_char.with_index do |cc,j| next unless cc == "." q = [[i,j]] while q.size > 0 sy, sx = q.shift c[sy][sx] = "b" $mm.push([sy,sx]) for i in 0..3 cy = sy + $dy[i] cx = sx + $dx[i] if c[cy][cx]=="." && cy.between?(0,h-1) && cx.between?(0,w-1) q.push([cy,cx]) end end end bl = true break end break if bl end ret = Float::INFINITY $m.each do |p| $mm.each do |pp| t = (p[0] - pp[0]).abs + (p[1] - pp[1]).abs - 1 ret = t if t < ret end end p ret