B. Find the Spruce(dfs+记忆化)

B. Find the Spruce(dfs+记忆化)

题目
题意：*是一棵树以及类似图片那里的树有多少个

从上往下搜索每一个点，看从这个点往下能够构成树的深度，加起来就是答案

#include<bits/stdc++.h>
using namespace std;
const int maxn = 1e5+5;
string s[600];
int dp[600][600];//储存dfs的值
int sum=0,n,m;
int dfs(int x,int y){//dfs求树的深度if(dp[x][y]) return dp[x][y];//如果搜索过就返回dpint flag=0;//判断是否能继续往下if(x+1<n&&y-1>=0&&y+1<m){if((s[x+1][y]=='*')&&(s[x+1][y-1]=='*')&&(s[x+1][y+1]=='*')){flag=1;}}if(flag) return dp[x][y]=1+min(min(dfs(x+1,y),dfs(x+1,y-1)),dfs(x+1,y+1));//因为要保证树完整所以要求最小的树的深度else return dp[x][y]=1;//深度为1即一个点
}
int main(){ios::sync_with_stdio(0);int t;cin>>t;while(t--){memset(dp,0,sizeof(dp));cin>>n>>m;sum=0;for(int i=0;i<n;i++){cin>>s[i];}for(int i=0;i<n;i++){for(int j=0;j<m;j++){if(s[i][j]=='*'){sum+=dfs(i,j);}}}cout<<sum<<endl;}
}