【Codeforces 1461 B】Find the Spruce，矩阵图形统计，枚举，行前缀和

problem

B. Find the Spruce
time limit per test1 second
memory limit per test256 megabytes
inputstandard input
outputstandard output
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×m matrix consisting of “*” and “.”.

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≤i≤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:

Now Rick wants to know how many spruces his n×m matrix contains. Help Rick solve this problem.

Input
Each test contains one or more test cases. The first line contains the number of test cases t (1≤t≤10).

The first line of each test case contains two integers n and m (1≤n,m≤500) — matrix size.

Next n lines of each test case contain m characters ci,j — matrix contents. It is guaranteed that ci,j is either a “.” or an “*”.

It is guaranteed that the sum of n⋅m over all test cases does not exceed 5002 (∑n⋅m≤5002).

Output
For each test case, print single integer — the total number of spruces in the matrix.

Example
inputCopy
4
2 3
.*.

2 3
..
.
4 5
..

..*
5 7
….…
.*****.

.*****.
….…
outputCopy
5
3
23
34
Note
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).

solution

/*
题意：
+ 给出n*m（500）的矩阵，找有多少个云杉（1,3,5,2k-1个*构成的对称图形）
思路：
+ 就爆搜，遇到*就往下搜（10*550*500不会TLE的（bushi）），
+ 记得前缀和统计每行的*个数
*/
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const int maxn = 570;
int a[maxn][maxn];
int main(){
	ios::sync_with_stdio(false);
	int T;  cin>>T;
	while(T--){
		int n ,m;  cin>>n>>m;
		for(int i = 1; i <= n; i++)
			for(int j = 1; j <= m; j++)
				{char ch; cin>>ch; a[i][j]=a[i][j-1]+(ch=='*'?1:0);}
		int ans = 0;
		for(int i = 1; i <= n; i++){
			for(int j = 1; j <= m; j++){
				if(a[i][j]==0)continue;
				int kk = min(n-i,min(m-j,j+1));
				for(int k = 0; k <= kk; k++){
					if(a[i+k][j+k]-a[i+k][j-k-1]!=2*k+1)
						break;
					ans++;
				}
			}
		}
		cout<<ans<<"\n";
	}
	return 0;
}



  

 

  
 
 

  
1
  
2
  
3
  
4
  
5
  
6
  
7
  
8
  
9
  
10
  
11
  
12
  
13
  
14
  
15
  
16
  
17
  
18
  
19
  
20
  
21
  
22
  
23
  
24
  
25
  
26
  
27
  
28
  
29
  
30
  
31
  
32
  
33
  
34
  
35
  
36
  
37
  
38
 

文章来源: gwj1314.blog.csdn.net，作者：小哈里，版权归原作者所有，如需转载，请联系作者。

原文链接：gwj1314.blog.csdn.net/article/details/113482152