分数: 350 点
问题陈述
AtCoder 公司办公室表示为网格 H 行和 W 列。让 (i, j) 表示位于 i从顶部开始的第行和 j左起第 列。
每个单元格的状态由一个字符表示 S_{i,j}。如果 S_{i,j} is #,该单元格有墙;如果 S_{i,j} is .,该单元格是一层;如果 S_{i,j} is H,该单元在地板单元上放置了加湿器。
如果某个单元可以从至少一个加湿器单元至多到达,则该单元被视为已加湿 D 向上、向下、向左或向右移动,无需穿过墙壁。请注意,任何带有加湿器的电池都始终处于加湿状态。
查找加湿地板单元的数量。
约束
- 1 \leq H \leq 1000
- 1 \leq W \leq 1000
- 0 \leq D \leq H\times W
- S_{i,j} is
#,.,或H. (1 \leq i \leq H, 1 \leq j \leq W) - 所有输入数字均为整数。
输入
输入由标准输入按以下格式给出:
H W D
S_{1,1}S_{1,2}\cdotsS_{1,W}
S_{2,1}S_{2,2}\cdotsS_{2,W}
\vdots
S_{H,1}S_{H,2}\cdotsS_{H,W}
输出
打印答案。
示例输入 1
3 4 1 H... #..H .#.#
示例输出 1
5
五格 (1,1), (1,2), (1,4), (2,3), (2,4) 被加湿。
示例输入 2
5 6 2 ##...H H..... ..H.#. .HH... .###..
示例输出 2
21
示例输入 3
1 6 3 ...#..
示例输出 3
0
可能没有细胞被加湿。