CodeForces

CF1461B Find the Spruce

题目大意：

求指定类型图案的数量。

思路：

一个很巧妙的递推式。

注意从下往上进行递推。

Code:

#include <bits/stdc++.h>
using namespace std;
const int N = 510;

int n, m; 
char mp[N][N];
int dp[N][N];

int main() {
	int T; scanf("%d", &T);
	while (T--) {
		memset(dp, 0, sizeof(dp));
		int ans = 0;
		scanf("%d %d", &n, &m);
		for (int i = 1; i <= n; i++) {
			for (int j = 1; j <= m; j++) {
				scanf(" %c", &mp[i][j]);
			}
		}
		for (int i = n; i >= 1; i--) {
			for (int j = 1; j <= m; j++) {
				if (mp[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]));
					ans += dp[i][j];
				}
			}	
		}
		// for (int i = 1; i <= n; i++) {
		// 	for (int j = 1; j <= k; j++) {
		// 		cout << dp[i][j] << " ";
		// 	}
		// 	cout << endl;
		// }
		cout << ans << endl;
	}
	return 0;
}