まず、各行と各列に爆弾があるかを管理することで、全ての 安全な空マス を \(O(HW)\) で列挙できます。

計算量を気にしないのであれば各空きマスから BFS をして

• \(K\) 回以下の移動で 安全な空マス に到達できるか？

を解けばよいです。しかし、これでは \(\Theta((HW)^2)\) の計算量がかかってしまいます。よって、すべてのマスについて同時に求めるような工夫が必要です。

ところで、空きマス \((i, j)\) について以下の \(2\) つの条件は同値です。

• \(K\) 回以下の移動で 安全な空マス に到達できる

• ある 安全な空きマス \((r, c)\) であって、そのマスから \(K\) 回以下の移動で \((i, j)\) に到達できるようなものが存在する

よって、「もっとも近い 安全な空マス からの最短距離」を各 \((i, j)\) について求めれば良いです。これは全ての 安全な空マス を同時に始点とした、「多始点 BFS 」で出来ることが知られています。（通常の BFS は始点が \(1\) つですが、複数の頂点を距離 \(0\) の始点としたものを「多始点 BFS 」と呼びます。実装上は、はじめに距離を \(0\) として que に入れる頂点が複数になるのみです）

これによって、「もっとも近い 安全な空きマス までの距離」がすべての空きマスについて \(O(HW)\) で列挙できます。

あとは、これが \(K\) 以下か判定すればよいです。

実装例

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)