B. Find the Spruce （模拟 前缀和

B. Find the Spruce （模拟 前缀和

添加链接描述
看到题目范围很小 可以考虑n^3暴力枚举 先用前缀和统计每行的树的*个数，然后从当前开始枚举k的高度然后统计树的个数

#include<bits/stdc++.h>
using namespace std;
const int N=600;
char s[N][N];typedef long long ll;
void solve(){int n,m;int sum[N][N]={};scanf("%d%d",&n,&m);for(int i=1;i<=n;i++){scanf("%s",s[i]+1);}for(int i=1;i<=n;i++){for(int j=1;j<=m;j++){if(s[i][j]=='*'){sum[i][j]=sum[i][j-1]+1;}else sum[i][j]=sum[i][j];}}ll ans=0;for(int i=1;i<=n;i++){for(int j=1;j<=m;j++){if(s[i][j]=='*'){ans++;for(int k=i+1;k<=n;k++){if(j+k-i<=m&&j-k+i>0&&sum[k][j+k-i]-sum[k][j-k+i-1]==2*(k-i)+1)ans++;else break;}}}
}printf("%lldn",ans);
}int main(){int T;scanf("%d",&T);while(T--){solve();}return 0;
}