cf

1461B - Find the Spruce

// 关键思想 
对于顶点(i,j)能构成树的数量 == min(顶点(i + 1,j - 1)构成树的数量,顶点(i + 1,j)构成树的数量,顶点(i + 1,j + 1)构成树的数量) + 1

#include<iostream>
#include<cstring>
using namespace std;const int N = 510;
int d[N][N];int main()
{int t;cin >> t;while(t --){int n,m;cin >> n >> m;memset(d,0,sizeof d);for(int i = 1; i <= n; i ++)for(int j = 1; j <= m; j ++){char c;cin >> c;d[i][j] = (c == '*');}long long ans = 0;for(int i = n; i >= 1; i --)for(int j = 1; j <= m; j ++){if(d[i][j]) d[i][j] = min( min(d[i + 1][j - 1],d[i + 1][j]),d[i + 1][j + 1]) + 1;ans += d[i][j];}cout << ans << endl;}
}