← 返回题目列表

AtCoder · abc383_b

D. 加湿器2

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

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