题目描述

给定一个 $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$。

4
3 5 1
..#..
.###.
#####
3 5 1
.....
.....
.....
4 5 1
#####
#####
#####
#####
4 5 2
#####
#####
#####
#####

Case #1: 9
Case #2: 0
Case #3: 9
Case #4: 10

提示

限制条件

$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 完成