分数: 250 点
问题陈述
AtCoder 公司办公室可以表示为一个网格 H 行和 W 列。让 (i, j) 表示位于 i从顶部开始的第行和 j左起第 列。
每个单元格的状态由一个字符表示 S_{i,j}。如果 S_{i,j} is #,该单元格包含一张桌子;如果 S_{i,j} is .,该单元格是一层。保证至少有两个楼层单元。
您将选择两个不同的地板单元并在每个单元上放置一个加湿器。
放置加湿器后,电池 (i,j) 被加湿当且仅当它在曼哈顿距离内 D 来自至少一个加湿器单元 (i',j')。曼哈顿 之间的距离 (i,j) 和 (i',j') 定义为 |i - i'| + |j - j'|。 请注意,放置加湿器的任何地板单元始终处于加湿状态。
找出加湿地板单元的最大可能数量。
约束
- 1 \leq H \leq 10
- 1 \leq W \leq 10
- 2 \leq H \times W
- 0 \leq D \leq H+W-2
- H,W,D 是整数。
- S_{i,j} is
#or.. (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
2 5 1 .###. .#.##
示例输出 1
3
将加湿器打开时 (1,1) 和 (1,5):
- 从加湿器上 (1,1),两个单元格 (1,1) 和 (2,1) 被加湿。
- 从加湿器上 (1,5),一个单元格 (1,5) 已加湿。
总共三个单元被加湿。没有任何配置可以加湿四个或更多地板单元,所以答案是 3.
示例输入 2
5 5 2 .#.#. ..... .#.#. #.#.# .....
示例输出 2
15
将加湿器打开时 (2,4) 和 (5,3), 15 地板单元已加湿。
示例输入 3
4 4 2 .... .##. .##. ....
示例输出 3
10