B. Find the Spruce(cf) dp

B. Find the Spruce(cf) dp

 题目大意：就是找有多少个图上的这些图形

其实可以从下往上看，如果这个点是‘*’,它本身就是一个；如果它的下方，下方左边，下方右边都是‘*’，那么又要加...想想看第三个图是不是应该是dp[i][j] += min(dp[i][j], dp[i + 1][j - 1], dp[i + 1][j + 1]),当然初始应该吧所有是‘*’地方的dp[i][j]设为1，'.'的dp[i][j]设为0。

#include<bits/stdc++.h>
using namespace std;
#define INF 0x3f3f3f3f
typedef pair<int, int> PII;
const double pi = acos(-1.0);
#define rep(i, n) for (int i = 1; i <= (n); ++i)
#define rrep(i, n) for (int i = n; i >= (1); --i)
typedef long long ll;
#define sqar(x) ((x)*(x))const int N = 510;
char a[N][N];
int dp[N][N];int main(){int t, n, m;cin >> t;while(t--){memset(dp, 0, sizeof dp);cin >> n >> m;rep(i,n) scanf("%s", a[i] + 1);rep(i, n) rep(j, m){if(a[i][j] == '*') dp[i][j] = 1;}ll res = 0;for(int i = n; i >= 1; i--){for(int j = 1; j <= m; j++){if(dp[i][j]) dp[i][j] += min(dp[i + 1][j], min(dp[i + 1][j - 1], dp[i + 1][j + 1]));res += dp[i][j];}}cout << res << endl;}return 0;
}