Find the Spruce(dp 动态规划）

are up soon. Rick that it’s time to think about a tree. But Rick doesn’t want real trees to get hurt so he to find some in an n×m of “*” and “.”.

To find every first let’s what a in the is. A set of cells is a of k with at point (x,y) if:

All cells in the set an “*”.

For each 1≤i≤k all cells with the row x+i−1 and in range [y−i+1,y+i−1] must be a part of the set. All other cells to the set.

of and trees:

Now Rick wants to know how many his n×m . Help Rick solve this .

Input

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

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

Next n lines of each test case m ci,j — . It is that ci,j is a “.” or an “*”.

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

For each test case, print — the total of in the .

Input

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

5
3
23
34

Note

In the first test case the first of 2 has its at point (1,2), the of 1 has its at point (1,2), the third of 1 has its at point (2,1), the of 1 has its at point (2,2), the fifth of 1 has its at point (2,3).

In the test case the first of 1 has its at point (1,2), the of 1 has its at point (2,1), the third of 1 has its at point (2,2).

其实标注也没啥用 就是让你求有多少个树(第一行1个第二行3个第三行5个。。。。。）

#include
#include
#include
#include
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("###%d\n",dp[i][j]);}}}printf("%d\n",sum);}return 0;
}