Find the Spruce

题目大意：

思路：

求出所有符合要求的图形。一开始想着枚举所有的点(i,j)，以点(i,j)为起点，向下不断寻找符合条件的图形，但是觉得太麻烦了。然后发现每一个点是否可以继续向下寻找符合条件的图形完全取决于点(i+1,j-1)、(i+1,j)、(i+1,j+1)这三个点是否都是 * ,并且点(i,j)可以向下找到几个符合条件的图形，也是取决于这三个点中最小的符合条件的图形的数量。这样完全可以从最后一行向上进行动态转移。一开始初始化所有为*的点(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])); 最后答案就是所有dp[i][j]之和。

代码：

#include
using namespace std;
const int maxn=500+50;
typedef long long ll;
ll T,n,m,dp[maxn][maxn];char s[maxn][maxn];
int main(){cin>>T;while(T--){cin>>n>>m;for(int i=1;i<=n;i++)cin>>s[i]+1;for(int i=1;i<=n;i++){for(int j=1;j<=m;j++){if(s[i][j]=='*'){dp[i][j]=1;}else{dp[i][j]=0;}}}ll tot=0;for(int i=n-1;i>=1;i--){for(int j=1;j<=m;j++){if(j-1>=1&&j+1<=m&&dp[i][j]==1&&dp[i+1][j-1]&&dp[i+1][j]&&dp[i+1][j+1]){dp[i][j]+=min(dp[i+1][j-1],min(dp[i+1][j],dp[i+1][j+1]));}}}for(int i=1;i<=n;i++){for(int j=1;j<=m;j++){tot+=dp[i][j];}}cout<<tot<<endl;}return 0;
}