P16619 [GKS 2017 #B] Christmas Tree

给定一个 $N$ 行 $M$ 列的矩形网格。每个格子被涂成两种颜色之一：绿色和白色。你的任务是找到该网格中最大的圣诞树中所包含的绿色格子数量。 为了定义圣诞树，首先定义**好三角形**如下： 以顶部位于第 $R$ 行、第 $C$ 列、高度为 $h$ 的好三角形是一个完全由绿色格子组成且尖朝上的等腰三角形。形式化地，这意味着：格子 $(R, C)$ 为绿色，并且对于每个 $i$ 从 $0$ 到 $h-1$（包含两端），第 $R+i$ 行中从第 $C-i$ 列到第 $C+i$ 列的所有格子均为绿色。 例如： ``` ..#.. .#### ##### ``` 是一个高度为 $3$ 的好三角形。其中 `#` 格子为绿色，`.` 格子为白色。注意，存在一个绿色格子不属于该好三角形，尽管它与好三角形相邻。 ``` ..#.. .###. ####. ``` **不是**一个好三角形，因为第 $3$ 行的第 $5$ 个格子是白色。然而，存在高度为 $2$ 的好三角形。 ``` ...#. .###. #####. ``` **不是**一个好三角形。然而，存在高度为 $2$ 的好三角形。 **$K$-圣诞树**定义如下： - 它恰好包含 $K$ 个垂直排列的好三角形。 - 第 $i+1$ 个三角形的顶部必须与第 $i$ 个三角形底边中某个格子的下边沿相接。这意味着，如果第 $i$ 个三角形的底边位于第 $r$ 行，从第 $c1$ 列到第 $c2$ 列，那么第 $i+1$ 个三角形的顶部必须位于第 $r+1$ 行，且列号在 $c1$ 到 $c2$ 之间（包含两端）。 例如，$K = 2$ 时： ``` ...#... ..###.. .#####. ####### ..#.... .###... #####.. ``` 是一个有效的 $2$-圣诞树。注意，两个好三角形的高度可以不同。 ``` ..#.. .###. .#... ``` 也是一个有效的 $2$-圣诞树。注意，好三角形的高度可以为 $1$，此时只包含一个绿色格子。 ``` ...#... ..###.. .#####. ....... ..#.... .###... #####.. ``` **不是**有效的圣诞树，因为第二个三角形必须从第 $4$ 行开始。 ``` ...#. ..### .#... ###.. ``` **不是**有效的圣诞树，因为第二个三角形的顶部必须位于第 $3$ 列到第 $5$ 列之间（包含两端）。 你需要找出包含绿色格子数最多的 $K$-圣诞树。

输入的第一行给出测试用例的数量 $T$。接下来有 $T$ 个测试用例。每个测试用例由三行组成： - 第一行包含三个空格分隔的整数 $N$、$M$ 和 $K$，其中 $N$ 是网格的行数，$M$ 是网格的列数，$K$ 是目标圣诞树中包含的好三角形的数量。 - 接下来的 $N$ 行，每行恰好包含 $M$ 个字符。每个字符要么是 `.`（表示白色格子），要么是 `#`（表示绿色格子）。

对于每个测试用例，输出一行，格式为 `Case #x: y`，其中 $x$ 是测试用例编号（从 $1$ 开始），$y$ 是最大的 $K$-圣诞树中所包含的绿色格子数量。如果不存在 $K$-圣诞树，则输出 $0$。

### 限制条件 $1 \le T \le 100$。 $1 \le M \le 100$。 $1 \le N \le 100$。 网格中的每个字符要么是 `.`，要么是 `#`。 **小数据集（测试集 1 – 可见）** $K = 1$。 **大数据集（测试集 2 – 隐藏）** $1 \le K \le 100$。 翻译由 DeepSeek V4 Pro 完成