Codeforces Round #689 (Div. 2）B. Find the Spruce

Codeforces Round #689 (Div. 2）B. Find the Spruce

Codeforces Round #689 (Div. 2）的其他题解点我

B. Find the Spruce

题目大意：
直接用vjudge上的了

思路：
我们在输入时把*标记为1（用一个新数组dp[i][j]）
然后疯狂枚举整个矩阵
如果一个带 * 的上面左边右边的值都相等，则中间+1
即
010
111
的情况
那么变成
010
121

多层的大概就是这样
00100
01210
12321

以此类推，然后由于每次改变会影响当前次数枚举（指枚举矩阵的次数）的后面的枚举
所以我们要先用一个数组存下上一次枚举（指枚举矩阵）的值
然后疯狂枚举就好
在每次值添加的时候ans加一
数据范围500
我们枚举500次
时间复杂度n^3

AC代码：

#include<cstdio>
#include<iostream>
#include<cstring>
#include<map>
#include<set>
#include<algorithm>
#define ll long long 
using namespace std;
const int maxn = 603;
char a[maxn][maxn];
int dp[maxn][maxn];
int pre[maxn][maxn];
int n, m;
int sum = 0;
int main() {int T;scanf("%d", &T);while (T--) {memset(dp,0,sizeof(dp));memset(pre, 0, sizeof(pre));scanf("%d %d", &n, &m);getchar();ll ans = 0;for (int i = 1; i <= n; ++i) {for (int j = 1; j <= m; ++j) {scanf("%c", &a[i][j]);if (a[i][j] == '*')ans++, dp[i][j] = 1;else dp[i][j] = 0;}getchar();}for (int t = 1; t <= 500;t++) {for (int i = 1; i <= n; ++i)for (int j = 1; j <= m; ++j)pre[i][j] = dp[i][j];for (int i = 1; i <= n; ++i) {for (int j = 1; j <= m; ++j) {if (a[i][j] != '*')continue;if (pre[i][j]&&pre[i - 1][j] == pre[i][j - 1]&& pre[i][j - 1]== pre[i][j + 1]&&pre[i][j+1]==pre[i][j])dp[i][j]++,ans++;}}}printf("%lldn",ans);}
}