AT_abc472_d [ABC472D] Bomber Mad

有一个 $H$ 行 $W$ 列的网格。每个格子可以是空格子或炸弹格子。我们用 $(i,j)$ 表示从上往下第 $i$ 行，从左往右第 $j$ 列的格子。网格由 $H$ 个长度为 $W$ 的字符串 $S_1, S_2 , \dots ,S_H$ 给出：如果 $S_i$ 的第 $j$ 个字符为 `.`，则 $(i,j)$ 是空格子；如果第 $j$ 个字符为 `#`，则 $(i,j)$ 是炸弹格子。 对于一个空格子 $(i,j)$，如果在第 $i$ 行和第 $j$ 列都没有炸弹格子，那么该格子被称为**安全空格子**。 每次移动，你可以从当前格子移动到上、下、左、右相邻的空格子（不能移动到炸弹格子）。请你计算满足以下条件的空格子 $(i,j)$ 的数量： - 能够在至多 $K$ 步内，从 $(i,j)$ 移动到某一个**安全空格子**。

输入按以下格式从标准输入给出： > $H$ $W$ $K$ > $S_1$ > $S_2$ > $\vdots$ > $S_H$

输出满足条件的空格子的数量。

### 样例解释 1 唯一的**安全空格子**是 $(2,2)$。有 $5$ 个空格子可以在不超过 $1$ 步内到达 $(2,2)$，分别是 $(1,2)$、$(2,1)$、$(2,2)$、$(2,3)$、$(3,2)$，因此答案为 $5$。 ### 样例解释 2 由于没有炸弹格子，所有 $6$ 个格子都是**安全空格子**。因此，每个空格子都满足条件，且所需步数为 $0$。 ### 数据范围 - $1 \le H,W \le 5\times 10^5$ - $H\times W \le 5\times 10^5$ - $0 \le K \le H\times W-1$ - $S_i$ 是由 `.` 和 `#` 组成的长度为 $W$ 的字符串 - $H$、$W$、$K$ 均为整数 由 ChatGPT 5 翻译