CF1461B Find the Spruce

假期即将来临。Rick 意识到是时候考虑购买一棵传统的云杉树了。但 Rick 不想伤害真正的树，所以他决定在一个 $n \times m$ 的矩阵中寻找一些由 “\*” 和 “.” 组成的云杉树。  在寻找每一棵云杉树之前，我们先来定义矩阵中的云杉树。若一组矩阵单元格构成了以点 $(x, y)$ 为起点、高度为 $k$ 的云杉树，则需满足： - 该集合内的所有单元格均为 “\*”。 - 对于每个 $1 \le i \le k$，所有第 $x+i-1$ 行、列号在 $[y-i+1, y+i-1]$ 范围内的单元格都属于该集合。其他单元格不能属于该集合。 以下是正确和错误的云杉树示例：  现在 Rick 想知道他的 $n \times m$ 矩阵中一共有多少棵云杉树。请你帮助 Rick 解决这个问题。

每组测试数据包含一个或多个测试用例。第一行为测试用例数 $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$）。

对于每个测试用例，输出一个整数，表示矩阵中云杉树的总数。

在第一个测试用例中，高度为 $2$ 的第一棵云杉树的起点在 $(1, 2)$，高度为 $1$ 的第二棵云杉树的起点也在 $(1, 2)$，高度为 $1$ 的第三棵云杉树的起点在 $(2, 1)$，高度为 $1$ 的第四棵云杉树的起点在 $(2, 2)$，高度为 $1$ 的第五棵云杉树的起点在 $(2, 3)$。 在第二个测试用例中，高度为 $1$ 的第一棵云杉树的起点在 $(1, 2)$，高度为 $1$ 的第二棵云杉树的起点在 $(2, 1)$，高度为 $1$ 的第三棵云杉树的起点在 $(2, 2)$。 由 ChatGPT 4.1 翻译