社区讨论

求问ABC的B题

学术版参与者 6已保存回复 12

讨论操作

快速查看讨论及其快照的属性,并进行相关操作。

当前回复
12 条
当前快照
1 份
快照标识符
@mhiyk76t
此快照首次捕获于
2025/11/03 17:49
4 个月前
此快照最后确认于
2025/11/18 11:12
4 个月前
查看原帖
我的B题代码是这样的:
CPP
#include<bits/stdc++.h>
using namespace std;
bool v[2005][15][15];
bool c[1100][110];
int n, cnt = 0, m, ans;
bool pan(int x, int y) {
	bool flag=0;
	for (int k = 1; k <= cnt; k++) {
		int flag2=1;
		for (int j = x; j <= x + m - 1; j++) {
			for (int i = y; i <= y + m - 1; i++) {
				if (v[k][j - x + 1][i - y + 1] != c[j][i]) {
					flag2=0;
				}
			}
		}
		if(flag2==1) flag=1;
	}
	if (!flag) {
		cnt++;
		for (int l = 1; l <= m; l++) {
			for (int r = 1; r <= m; r++) {
				v[cnt][l][r] = c[l + x - 1][r + y - 1];
			}
		}
		return 0;
	}
	return 1;
}
void dfs() {
	for (int i = 1; i <= n - m + 1; i++) {
		for (int j = 1; j <= n - m + 1; j++) {
			if (!pan(i, j)) {
				ans++;
			}
		}
	}
}
int main() {
	cin >> n >> m;
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= n; j++) {
			char x;
			cin >> x;
			if ( x == '#') c[i][j] = 1;
			else c[i][j] = 0;
		}
	}
	dfs();
	cout << ans;
	return 0;
}
这是本蒟蒻用暴力做的,虽然只运行了 1ms1ms,AC了,但是请问有没有代码量更少(不算把2行的回车删掉,缩成1行的),或者时间复杂度更低(剪枝可以),或者空间复杂度更低的解法?
违规紫衫,如果提供帮助闭关。

回复

12 条回复,欢迎继续交流。

正在加载回复...