社区讨论
求问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;
}
这是本蒟蒻用暴力做的,虽然只运行了 ,AC了,但是请问有没有代码量更少(不算把2行的回车删掉,缩成1行的),或者时间复杂度更低(剪枝可以),或者空间复杂度更低的解法?
违规紫衫,如果提供帮助闭关。
回复
共 12 条回复,欢迎继续交流。
正在加载回复...