← 返回题目列表

Codeforces · 1461/B

B. 找到云杉

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

假期很快就要到了。里克意识到是时候考虑购买一棵传统的云杉树了。但 Rick 不希望真正的树木受到伤害,因此他决定在由“*”和“.”组成的 $$$n \times m$$$ 矩阵中找到一些树木。

为了找到每个云杉,首先让我们定义矩阵中的云杉是什么。一组矩阵单元称为高度为 $$$k$$$ 且原点为点 $$$(x, y)$$$ 的云杉,如果:

- 集合中的所有单元格都包含“*”。
- 对于每个 $$$1 \le i \le k$$$,行号为 $$$x+i-1$$$ 且列号在 $$$[y - i + 1, y + i - 1]$$$ 范围内的所有单元格必须是该集合的一部分。所有其他单元格不能属于该集合。

正确和错误云杉树的示例:

现在 Rick 想知道他的 $$$n \times m$$$ 矩阵包含多少棵云杉。帮助瑞克解决这个问题。

输入

每个测试都包含一个或多个测试用例。第一行包含测试用例的数量 $$$t$$$ ($$$1 \le t \le 10$$$)。

每个测试用例的第一行包含两个整数 $$$n$$$ 和 $$$m$$$ ($$$1 \le n, m \le 500$$$) - 矩阵大小。

每个测试用例的接下来 $$$n$$$ 行包含 $$$m$$$ 个字符 $$$c_{i, j}$$$ — 矩阵内容。保证 $$$c_{i, j}$$$ 是“.”。或“*”。

保证所有测试用例的 $$$n \cdot m$$$ 总和不超过 $$$500^2$$$ ($$$\sum n \cdot m \le 500^2$$$)。

输出

对于每个测试用例,打印单个整数 - 矩阵中云杉的总数。

示例

输入 #1

4
2 3
.*.
***
2 3
.*.
**.
4 5
.***.
*****
*****
*.*.*
5 7
..*.*..
.*****.
*******
.*****.
..*.*..

输出 #1

5
3
23
34

注意

在第一个测试用例中,第一棵高度为 $$$2$$$ 的云杉的原点为 $$$(1, 2)$$$,第二棵高度为 $$$1$$$ 的云杉的原点为 $$$(1, 2)$$$,第三棵高度为 $$$1$$$ 的云杉的原点为点 $$$(2, 1)$$$,第四棵高度为 $$$1$$$ 的云杉的原点为点 $$$(2, 1)$$$,第四棵云杉的高度为 $$$1$$$。高度为 $$$1$$$ 的云杉的原点为点 $$$(2, 2)$$$,高度为 $$$1$$$ 的第五颗云杉的原点为点 $$$(2, 3)$$$。

在第二个测试用例中,高度为 $$$1$$$ 的第一棵云杉的原点为 $$$(1, 2)$$$,高度为 $$$1$$$ 的第二棵云杉的原点为 $$$(2, 1)$$$,高度为 $$$1$$$ 的第三棵云杉的原点为 $$$(2, 2)$$$。