← 返回题目
题库练习 Bomber Mad
← 上一题 下一题 →

A7721 | Bomber Mad

时间限制2s
内存限制1024MB
通过 / 提交0/0

题目描述

有一个 $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$ 列中均不存在炸弹格子，则称该格子为**安全空格子**。

每次移动，你可以从当前格子向其上方、下方、左方或右方的相邻空格子移动（不能移向炸弹格子）。请找出满足以下条件的空格子 $(i, j)$ 的数量：

* 从 $(i,j)$ 出发，至多经过 $K$ 次移动即可到达某个**安全空格子**。

输入格式

输入从标准输入中按以下格式给出：

> $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
C++ 编辑器
输入
输出