CF1921G Mischievous Shooter

有一次，调皮捣蛋的射手 Shel 来到一个大小为 $n \times m$ 的矩形场地上，这个场地被划分为若干个单位方格。每个格子里要么有一个目标，要么没有。 Shel 只有一把幸运的猎枪，他可以向四个方向之一射击：右下、左下、左上或右上。每次射击时，猎枪会击中所选方向上所有曼哈顿距离不超过固定常数 $k$ 的目标。两点 $(x_1, y_1)$ 和 $(x_2, y_2)$ 之间的曼哈顿距离定义为 $|x_1 - x_2| + |y_1 - y_2|$。  $k = 3$ 时可能的击中区域。 Shel 的目标是用一次射击击中尽可能多的目标。请你帮他计算这个最大值。

每组测试数据包含若干个测试用例。第一行包含一个整数 $t$（$1 \le t \le 1000$），表示测试用例的数量。接下来是每个测试用例的描述。 每个测试用例的第一行包含三个整数 $n$、$m$ 和猎枪威力常数 $k$（$1 \le n, m, k \le 10^5, 1 \le n \cdot m \le 10^5$）。 接下来的 $n$ 行，每行包含 $m$ 个字符，描述场地的每一行。其中字符 '.' 表示该格为空，字符 '#' 表示该格有目标。 保证所有测试用例中 $n \cdot m$ 的总和不超过 $10^5$。

对于每个测试用例，输出一个整数，表示用一次射击最多能击中的目标数，每个结果占一行。

对于题目描述中的样例，可能的最优射击如下图所示：  由 ChatGPT 4.1 翻译