题目链接

https://vjudge.net/contest/413174#problem/B

解题思路

dp。
dp[i][j]表示以点(i,j)为树顶的树的个数，最后求一下所有位置的点为树顶能构成的树的个数之和，即为答案。
转移方程：开始所有为 * 的位置全部初始化为1，dp[i][j]+=min{dp[i+1][j-1],dp[i+1][j],dp[i+1][j+1]}
注意：
1.边界；
2.因为给出的是n * m的范围，所以我们要用一维数组存储二维信息，不细说了，一维数组的下标整除m表示行坐标，取余m表示列坐标，行列坐标均从0开始。dp数组要设置成一维的。
3.一个一个输入字符的时候，也要注意getchar收回回车。

AC代码

#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int N=300000;
ll dp[N];
char mp[N];
int main()
{
    int t;
    cin>>t;
    while(t--)
    {
        memset(dp,0,sizeof dp);
        ll ans=0;
        int n,m,k=0;
        cin>>n>>m;
        getchar();//getchar()!!
        for(int i=0;i<n;i++,getchar())//getchar()!!
        for(int j=0;j<m;j++)
        scanf("%c",&mp[i*m+j]);

        for(int i=n-1;i>=0;i--)
        for(int j=0;j<m;j++)
        {
            if(mp[i*m+j]=='.') continue;
            dp[i*m+j]=1;
            if(i!=n-1 && j!=0 && j!=m-1) 
            dp[i*m+j]+=min(dp[(i+1)*m+(j-1)],min(dp[(i+1)*m+j],dp[(i+1)*m+j+1]));
            ans+=dp[i*m+j];
        }
//        for(int i=0;i<n;i++,cout<<endl)
//        for(int j=0;j<m;j++)
//        cout<<dp[i*m+j]<<' ';
        cout<<ans<<endl;
    }
}

总结

不小心看到了是dp
直接一套组合拳，写完了，就是处理边界和数组存储花了好长时间。