Submission #885000

---

Source Code Expand

r, c, k = gets.split.map(&:to_i)

k -= 1

queue = []
min_dist = Array.new(r) { Array.new(c, r * c) }

r.times do |i|
  s = gets.chomp
  c.times do |j|
    if s[j] == 'x'
      queue << [i, j]
      min_dist[i][j] = 0
    end
  end
end

# dy = [1, -1, 0, 0]
# dx = [0, 0, 1, -1]
dxy = [[1, 0], [0, 1], [-1, 0], [0, -1]]
until queue.empty? do
  y, x = queue.shift
  # 4.times do |i|
  dxy.each do |dy, dx|
    ny = y + dy
    nx = x + dx
    # ny = y + dy[i]
    # nx = x + dx[i]
    # next unless ny.between?(0, r - 1)
    # next unless nx.between?(0, c - 1)
    next unless 0 <= ny && ny < r
    next unless 0 <= nx && nx < c
    next unless min_dist[ny][nx] > min_dist[y][x] + 1
    min_dist[ny][nx] = min_dist[y][x] + 1
    next unless min_dist[ny][nx] < k
    queue << [ny, nx]
  end
end

ans = 0
# for i in k...(r - k) do
#   for j in k...(c - k) do
#     ans += 1 if min_dist[i][j] > k
#   end
# end

for i in k...(r - k) do
  ans += min_dist[i][k...(c - k)].count { |v| v > k }
end

puts ans

Submission Info

Judge Result