First, by managing whether each row and each column contains a bomb, we can enumerate all safe empty cells in \(O(HW)\) time.

If we ignore the computational cost, we can BFS (Breadth-First Search) from each to solve:

• Can we reach to a safe empty cell with \(K\) moves or less?

However, this costs \(\Theta((HW)^2)\) time. Therefore, we need a way to process all cells simultaneously.

By the way, for a cell \((i, j)\), the following two conditions are equivalent:

• One can reach from there to a safe empty cell with \(K\) moves or less.

• There exists a safe empty cell \((r, c)\) such that one can reach from that cell to \((i, j)\) with \(K\) moves or less.

Thus, it is sufficient to find the shortest distance from the nearest safe empty cell for all \((i, j)\). It is known that we can use “multi-source BFS,” starting from all safe empty cells simultaneously. (In an ordinary BFS, there is only one starting point; meanwhile, a multi-source BFS starts from multiple vertices, all assumed to have distance \(0\). The only difference in implementation is that we now have multiple vertices inserted to the queue with distance \(0\).

Hence, the distance to the nearest safe empty cell can be enumerated in a total of \(O(HW)\) time.

All that left is to check if this value is \(K\) or less.

Sample code

from collections import deque

h, w, k = map(int, input().split())
s = [input() for _ in range(h)]

r = [0] * h
c = [0] * w
for i in range(h):
    for j in range(w):
        if s[i][j] == "#":
            r[i] = 1
            c[j] = 1

d = [[-1] * w for i in range(h)]
q = deque()
for i in range(h):
    for j in range(w):
        if r[i] == c[j] == 0:
            d[i][j] = 0
            q.append((i, j))

ans = 0
while q:
    i, j = q.popleft()
    if d[i][j] <= k:
        ans += 1
    for ni, nj in ((i-1, j), (i+1, j), (i, j-1), (i, j+1)):
        if 0 <= ni < h and 0 <= nj < w:
            if s[ni][nj] == "." and d[ni][nj] == -1:
                d[ni][nj] = d[i][j] + 1
                q.append((ni, nj))

print(ans)