疯狂炸弹手AI (CI翻译)
Problem Statement
题目描述
AI (CI翻译)There is a grid with $H$ rows and $W$ columns. Each cell is an empty cell or a bomb cell. Let $(i,j)$ denote the cell at the $i$-th row from the top and the $j$-th column from the left. The grid is given by $H$ length-$W$ strings $S_1, S_2 , \dots ,S_H$: if the $j$-th character of $S_i$ is ., $(i,j)$ is an empty cell, and if the $j$-th character of $S_i$ is #, $(i,j)$ is a bomb cell.
有一个 $H$ 行 $W$ 列的网格。每个格子要么是空格子，要么是炸弹格子。用 $(i,j)$ 表示从上往下第 $i$ 行、从左往右第 $j$ 列的格子。网格由 $H$ 个长度为 $W$ 的字符串 $S_1, S_2 , \dots ,S_H$ 给出：如果 $S_i$ 的第 $j$ 个字符是 .，则 $(i,j)$ 是空格子；如果 $S_i$ 的第 $j$ 个字符是 #，则 $(i,j)$ 是炸弹格子。AI (CI翻译)
For an empty cell $(i,j)$, if there is no bomb cell in the $i$-th row nor in the $j$-th column, that cell is called a safe empty cell.
对于空格子 $(i,j)$，如果第 $i$ 行和第 $j$ 列中都不存在炸弹格子，则称该格子为安全空格子。AI (CI翻译)
In one move, you can move from the current cell to an adjacent empty cell in the up, down, left, or right direction (you cannot move to a bomb cell). Find the number of empty cells $(i, j)$ satisfying the following condition:
一次移动中，你可以从当前格子向上、下、左、右四个方向之一移动到相邻的空格子（不能移动到炸弹格子）。请求出满足以下条件的空格子 $(i,j)$ 的数量：AI (CI翻译)
- A safe empty cell can be reached from
$(i,j)$in at most$K$moves.
- 从
$(i,j)$出发，至多移动$K$次可以到达一个安全空格子。
Constraints
约束条件
AI (CI翻译)$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$is a string of length$W$consisting of.and#.$H$,$W$, and$K$are integers.
$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$均为整数。
Input
输入格式
AI (CI翻译)The input is given from Standard Input in the following format:
输入从标准输入按以下格式给出：AI (CI翻译)
H W K
S_1
S_2
\vdots
S_HH W K
S_1
S_2
\vdots
S_HOutput
输出格式
AI (CI翻译)Output the number of empty cells satisfying the condition.
输出满足条件的空格子的数量。AI (CI翻译)
样例
3 3 1
#..
...
..#
5
2 3 0
...
...
6
5 7 2
..#....
..#....
.......
...#...
...#...
29
题面与样例版权归 AtCoder 及出题人所有；中文翻译由 AI 生成（gpt-6.1-sol），如有出入请以原文为准。