← 返回题目列表

AtCoder · abc383_c

F. 加湿器3

中文机器翻译题面 查看原题

分数: 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

可能没有细胞被加湿。