A7721. Bomber Mad
编程题
入门
知识点
题目描述
有一个 $H$ 行 $W$ 列的网格。每个格子要么是空格子，要么是炸弹格子。记 $(i,j)$ 为从上往下数第 $i$ 行、从左往右数第 $j$ 列的格子。该网格由 $H$ 个长度为 $W$ 的字符串 $S_1, S_2 , \dots ,S_H$ 给出：若 $S_i$ 的第 $j$ 个字符为
对于一个空格子 $(i,j)$，若其所在的第 $i$ 行和第 $j$ 列中均不存在炸弹格子，则称该格子为**安全空格子**。
每次移动，你可以从当前格子向其上方、下方、左方或右方的相邻空格子移动（不能移向炸弹格子）。请找出满足以下条件的空格子 $(i, j)$ 的数量：
* 从 $(i,j)$ 出发，至多经过 $K$ 次移动即可到达某个**安全空格子**。
.，则 $(i,j)$ 是空格子；若为 #，则 $(i,j)$ 是炸弹格子。对于一个空格子 $(i,j)$，若其所在的第 $i$ 行和第 $j$ 列中均不存在炸弹格子，则称该格子为**安全空格子**。
每次移动，你可以从当前格子向其上方、下方、左方或右方的相邻空格子移动（不能移向炸弹格子）。请找出满足以下条件的空格子 $(i, j)$ 的数量：
* 从 $(i,j)$ 出发，至多经过 $K$ 次移动即可到达某个**安全空格子**。
输入格式
输入从标准输入中按以下格式给出：
> $H$ $W$ $K$
> $S_1$
> $S_2$
> $\vdots$
> $S_H$
> $H$ $W$ $K$
> $S_1$
> $S_2$
> $\vdots$
> $S_H$
输出格式
输出满足条件的空单元格数量。
输入输出样例
输入 #1
3 3 1 #.. ... ..#
输出 #1
5
输入 #2
2 3 0 ... ...
输出 #2
6
输入 #3
5 7 2 ..#.... ..#.... ....... ...#... ...#...
输出 #3
29
说明/提示
**样例 1 解释：**
唯一的**安全空单元格**是 $(2,2)$。从五个空单元格 $(1,2),(2,1),(2,2),(2,3),(3,2)$ 出发，至多经过一步移动即可到达 $(2,2)$，因此答案为 $5$。
**样例 2 解释：**
由于不存在炸弹单元格，全部六个单元格均为**安全空单元格**。因此，每个空单元格均满足条件（所需移动步数为零）。
### 约束条件
* $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$ 均为整数。
唯一的**安全空单元格**是 $(2,2)$。从五个空单元格 $(1,2),(2,1),(2,2),(2,3),(3,2)$ 出发，至多经过一步移动即可到达 $(2,2)$，因此答案为 $5$。
**样例 2 解释：**
由于不存在炸弹单元格，全部六个单元格均为**安全空单元格**。因此，每个空单元格均满足条件（所需移动步数为零）。
### 约束条件
* $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$ 均为整数。