← 返回题目列表

Codeforces · 2113/C

C. 斯米洛和我的世界

中文机器翻译题面 查看原题

男孩 Smilo 正在玩 Minecraft!为了准备与巨龙的战斗,他需要大量的金苹果,为此,他需要大量的黄金。因此,斯米洛去了矿井。

矿井是一个大小为 $$$n \times m$$$ 的矩形网格,其中每个单元格可以是金矿石、石头或空单元格。斯米洛可以炸毁任何空牢房中的炸药。当炸药在坐标为 $$$(x, y)$$$ 的空单元格中爆炸时,以单元格 $$$(x, y)$$$ 为中心、边长 $$$2k + 1$$$ 的正方形内的所有单元格都会变空。如果找到金矿石 严格在里面 这个正方形(不在边界上),它消失了。然而,如果金矿石位于该正方形的边界上,斯米洛就会收集该金子。

炸药只能在矿井内引爆,但爆炸方块可以延伸到矿井边界之外。

确定 Smilo 可以收集的最大金币数量。

输入

每个测试包含多个测试用例。第一行包含测试用例的数量 $$$t$$$ ($$$1 \le t \le 10^4$$$)。测试用例的描述如下。

每个测试用例的第一行包含三个整数 $$$n$$$、$$$m$$$ 和 $$$k$$$ ($$$1 \leq n, m, k \leq 500$$$) — 分别是行数、列数和爆炸参数 $$$k$$$。

以下 $$$n$$$ 行均包含 $$$m$$$ 个字符,每个字符等于 '.', '#',或 'g',其中 '.' — 是一个空单元格, '#' — 是石头, 'g' — 是黄金。保证至少有一个单元格是空的。

保证所有测试用例的总和 $$$n \cdot m$$$ 不超过 $$$2.5 \cdot 10^5$$$。

输出

对于每个测试用例,输出一个整数——可以获得的最大黄金数量。

示例

输入
复制

3
2 3 1
#.#
g.g
2 3 2
#.#
g.g
3 4 2
.gg.
g..#
g##.

输出
复制

2
0
4

注意

在第一个测试用例中,Smilo 可以引爆任何空单元格中的炸药并获得 $$$2$$$ 金币:

在第二个测试用例中,无论Smilo做什么,他都无法获得任何金币:

在第三个测试用例中,可以引爆右下角的炸药以获得$$$2$$$金币,然后在左侧一个单元格再次爆炸以获得剩余的$$$2$$$金币: