AT_abc383_b [ABC383B] Humidifier 2

AtCoder 社的办公室可以用 $H$ 行 $W$ 列的网格表示。从上到下的第 $i$ 行，从左到右的第 $j$ 列的格子记作 $(i, j)$。 每个格子的状态由字符 $S_{i,j}$ 表示，若 $S_{i,j}$ 为 `#`，则该格子为桌子；若为 `.`，则为地板。保证地板格子的数量不少于 $2$。 你需要从所有地板格子中选出两个不同的格子，分别放置加湿器。 当加湿器被放置后，某个格子 $(i, j)$ 若与某个加湿器所在的格子 $(i', j')$ 的曼哈顿距离不超过 $D$，则该格子会被加湿。曼哈顿距离定义为 $|i - i'| + |j - j'|$。注意，加湿器放置的地板格子一定会被加湿。 请你求出可以被加湿的地板格子的最大可能数量。

输入按以下格式从标准输入读入。 > $H$ $W$ $D$ > $S_{1,1} S_{1,2} \cdots S_{1,W}$ > $S_{2,1} S_{2,2} \cdots S_{2,W}$ > $\vdots$ > $S_{H,1} S_{H,2} \cdots S_{H,W}$

请输出答案。

## 限制条件 - $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}$ 仅为 `#` 或 `.`，其中 $1 \leq i \leq H, 1 \leq j \leq W$ - 地板格子的数量不少于 $2$ ## 样例解释 1 当在格子 $(1,1)$ 和 $(1,5)$ 放置加湿器时： - 由于 $(1,1)$ 的加湿器，$(1,1)$ 和 $(2,1)$ 这两个格子会被加湿。 - 由于 $(1,5)$ 的加湿器，$(1,5)$ 这个格子会被加湿。 因此，共有 $3$ 个格子被加湿。不存在能加湿 $4$ 个或更多格子的放置方式，所以答案为 $3$。 ## 样例解释 2 当在格子 $(2,4)$ 和 $(5,3)$ 放置加湿器时，可以加湿 $15$ 个地板格子。 由 ChatGPT 4.1 翻译