Find the Spruce
题意翻译
给定一个大小为 $n\times m$ 的矩阵,矩阵仅包含字符 `.` 或字符 `*`.现在我们要找出这个矩形中所有大小的"松树"的数量.
我们规定这个矩形中一个矩形的点集被称作一个"根部点"位于$(x,y)$的大小为 $k$ 的"松树" 仅当:
- 这棵"松树"所有的位置均位于矩形的 `*` 字符上.
- 对于所有的 $i$ 满足 $1\leq i\leq k$, $u=x+i-1,v\in[y-i+1,y+i-1]$ 的位置 $(u,v)$ 均属于这个点集,而所有其他位置都不属于这个点集.
(上面的图表示了一些"松树"与非"松树"的例子,其中前三个分别为大小为 $1,2,3$ 的"松树",他们的"根部点"均为最底部一行的中间位置.)
求出所有大小的"松树"的数量.
$T$组数据.
保证数据有:
$1\leq T\leq 10.$
$1\leq n,m\leq 500,\sum n\times m\leq 250,000.$
矩形的所有位置均由 `.` 或 `*` 构成.
题目描述
Holidays are coming up really soon. Rick realized that it's time to think about buying a traditional spruce tree. But Rick doesn't want real trees to get hurt so he decided to find some in an $ n \times m $ matrix consisting of "\*" and ".".
![](https://cdn.luogu.com.cn/upload/vjudge_pic/CF1461B/0f830498ab169a471030eeb85fc12c395e76f5ca.png)To find every spruce first let's define what a spruce in the matrix is. A set of matrix cells is called a spruce of height $ k $ with origin at point $ (x, y) $ if:
- All cells in the set contain an "\*".
- For each $ 1 \le i \le k $ all cells with the row number $ x+i-1 $ and columns in range $ [y - i + 1, y + i - 1] $ must be a part of the set. All other cells cannot belong to the set.
Examples of correct and incorrect spruce trees:
![](https://cdn.luogu.com.cn/upload/vjudge_pic/CF1461B/2ce2df8e09c4fc74a3e149e5906821e41a5e552f.png)Now Rick wants to know how many spruces his $ n \times m $ matrix contains. Help Rick solve this problem.
输入输出格式
输入格式
Each test contains one or more test cases. The first line contains the number of test cases $ t $ ( $ 1 \le t \le 10 $ ).
The first line of each test case contains two integers $ n $ and $ m $ ( $ 1 \le n, m \le 500 $ ) — matrix size.
Next $ n $ lines of each test case contain $ m $ characters $ c_{i, j} $ — matrix contents. It is guaranteed that $ c_{i, j} $ is either a "." or an "\*".
It is guaranteed that the sum of $ n \cdot m $ over all test cases does not exceed $ 500^2 $ ( $ \sum n \cdot m \le 500^2 $ ).
输出格式
For each test case, print single integer — the total number of spruces in the matrix.
输入输出样例
输入样例 #1
4
2 3
.*.
***
2 3
.*.
**.
4 5
.***.
*****
*****
*.*.*
5 7
..*.*..
.*****.
*******
.*****.
..*.*..
输出样例 #1
5
3
23
34
说明
In the first test case the first spruce of height $ 2 $ has its origin at point $ (1, 2) $ , the second spruce of height $ 1 $ has its origin at point $ (1, 2) $ , the third spruce of height $ 1 $ has its origin at point $ (2, 1) $ , the fourth spruce of height $ 1 $ has its origin at point $ (2, 2) $ , the fifth spruce of height $ 1 $ has its origin at point $ (2, 3) $ .
In the second test case the first spruce of height $ 1 $ has its origin at point $ (1, 2) $ , the second spruce of height $ 1 $ has its origin at point $ (2, 1) $ , the third spruce of height $ 1 $ has its origin at point $ (2, 2) $ .