原题传送门
前言
天啊!上一周刚刚考完 \(CSP-J\) ,这一周就得去考 \(GESP\) 4级 (是的,你没有听错,我3级过了!)
所以,做了一道简单的题之后,我又来写题解了!
(仍然是WA++)
题目解析
哇,这题可真长啊!什么 (可恶的) 小杨有一个 \(n\) 行 \(m\) 列的网格图,其中每个格子要么是白色,要么是黑色……之类的。简单总结一下:
- 每一个测试点里有一共 \(t\) 组数据,老规矩:用
memset()
做初始化。 - 每组测试数据包含:一个 \(n\) 和 \(m\) 以及一个大小为 \(n \times m\) 的二维矩阵。
- 让你找是否有一个如下的连续的子矩阵
(你应该知道连续子矩阵是啥意思吧?)
0000
0110
0110
0000
- 如果有,输出
Yes
否则,输出No
即可。
思路解析
这道题看似需要复杂的算法,实际上…… 看看这感人的数据规模:
对全部的测试数据,保证 \(1 \leq t\leq 10\),\(1 \leq n,m \leq 100\)。
也就是说,其实只需要模拟即可通过!
即,遍历所有的可能的子矩阵起点:
for (int i = 1; i <= n - 3; i++) {for (int j = 1; j <= m - 3; j++) {if (check(i, j))flag = true;}
}
接着在 check()
函数里去判断,以 (i,j)
为起点的 \(4 \times 4\) 矩阵是否合规。
bool check(int x, int y) {for (int i = 0; i < 4; i++) {for (int j = 0; j < 4; j++) {if (c[i + x][j + y] != g[i][j])return false;}}return true;
}
唉,同样是2024年9月的题,3级第一题(详见它)就如此难,暴力也过不了。
而4级的题目,就非常人性化!
AC Code
点击查看完整代码
#include <bits/stdc++.h>
using namespace std;
const int N = 110, M = 110;
int n, m;
int a[N][M];
int t;
int mp[4][4] = {{0, 0, 0, 0},{0, 1, 1, 0},{0, 1, 1, 0},{0, 0, 0, 0}
};bool check(int x, int y) {for (int i = 0; i < 4; i++) {for (int j = 0; j < 4; j++) {if (a[x + i][y + j] != mp[i][j]) {return false;}}}return true;
}int main() {cin >> t;while (t--) {memset(a, 0, sizeof(a));cin >> n >> m;for (int i = 1; i <= n; i++) {string s;cin >> s;for (int j = 1; j <= m; j++) {a[i][j] = s[j - 1] - '0';}}bool flag = false;for (int i = 1; i <= n - 3; i++) {for (int j = 1; j <= m - 3; j++) {if (check(i, j)) {flag = true;break;}}if (flag) break;}if (flag) cout << "Yes" << endl;else cout << "No" << endl;}return 0;
}
完结撒花!(补药再抄代码了!)