B. Find the Spruce（递推）

B. Find the Spruce（递推）

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).

#include <bits/stdc++.h>
typedef long long ll;
const ll mod = 9999999967;
using namespace std;
namespace fastIO {inline void input(int& res) {char c = getchar();res = 0;int f = 1;while (!isdigit(c)) { f ^= c == '-'; c = getchar(); }while (isdigit(c)) { res = (res << 3) + (res << 1) + (c ^ 48);c = getchar(); }res = f ? res : -res;}inline ll qpow(ll a, ll b) {ll ans = 1, base = a;while (b) {if (b & 1) ans = (ans * base % mod +mod )%mod;base = (base * base % mod + mod)%mod;b >>= 1;}return ans;}
}
using namespace fastIO;
const int N = 1e6 + 5;int Case,n,m;
char s[505][505];
int ans[505][505];int cal(int x,int y){int res = 0;int minn;ans[x][y]=1;if(x+1>n||y<2||y+1>m) return -1;minn = 0x3f3f3f3f;for(int i=y-1;i<=y+1;i++){minn = min(minn,ans[x+1][i]);}ans[x][y] += minn;return minn+1;
}void solve(){ll res = 0;scanf("%d %d",&n,&m);for(int i=1;i<=n;i++){getchar();scanf("%s",s[i]+1);}for(int i=n;i>=1;i--){for(int j=1;j<=m;j++){if(s[i][j]=='*') {if(cal(i,j)==-1) {res++;continue;}res += cal(i,j);}}}printf("%lldn",res);memset(ans,0,sizeof(ans));
}int main(){//init();Case=1;scanf("%d",&Case);while(Case--){solve();}return 0;
}