Find the Spruce(dp 动态规划）

Find the Spruce(dp 动态规划）

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
Input

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

Output

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).
其实标注也没啥用 就是让你求有多少个树(第一行1个第二行3个第三行5个。。。。。）

#include<stdio.h>
#include<algorithm>
#include<math.h>
#include<string.h>
using namespace std;
#define ll long long
const int N=1e6+10;
int dp[550][550];
char a[550][550];
int main()
{int m;scanf("%d",&m);while(m--){memset(dp,0,sizeof(dp));int n,k,sum=0;scanf("%d %d",&n,&k);for(int i=1;i<=n;i++)scanf("%s",a[i]+1);for(int i=n;i>=1;i--){for(int j=1;j<=k;j++){if(a[i][j]=='*'){dp[i][j]=1;dp[i][j]+=min(dp[i+1][j-1],min(dp[i+1]  [j],dp[i+1][j+1]));   //因为已经清空了 所以可以从最后一行遍历sum+=dp[i][j];//  printf("###%dn",dp[i][j]);}}}printf("%dn",sum);}return 0;
}