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 翻译