判断网格中是否存在满足特定花纹的 4 × 4 子矩形。
网格中每格是黑或白。请判断是否存在一个 4 行 4 列的子矩形,满足:
输入中 0 表示白色、1 表示黑色。存在输出 Yes,否则输出 No。
0 0 0 0 0 1 1 0 0 1 1 0 0 0 0 0
做法很直接:枚举所有可能的左上角位置,然后逐格比对这 16 个格子。
模板匹配4×4 窗口字符比对多组测试
| 项目 | 说明 |
|---|---|
| 输入 | 第一行 t;每组先一行 n、m,再 n 行 01 串 |
| 输出 | 每组一行 Yes 或 No |
| 数据范围 | t ≤ 10,1 ≤ n, m ≤ 100 |
| 编码 | 0 = 白色,1 = 黑色 |
| 窗口尺寸 | 固定 4 行 4 列 |
样例答案依次是 No、Yes、No。
只有 1 行,而图案需要 4 行
根本没有 4 × 4 的子矩形
❌ No(尺寸不够)
网格中第 1~4 行、第 1~4 列恰好是:
0000(第 1 行)
0110(第 2 行)
0110(第 3 行)
0000(第 4 行)
与目标模板逐格一致
✅ Yes
网格为 00000 / 01100 / 01110 / 00001 / 01100
候选 1(第 1~4 行、第 1~4 列):
0000 / 0110 / 0111 / 0000
第 3 行是 0111,而模板要求 0110 ✗
候选 2(第 1~4 行、第 2~5 列):
0000 / 1100 / 1110 / 0001
第 2 行是 1100,而模板要求 0110 ✗
其余候选同样不匹配
❌ No
| 行 | 第 1 列 | 第 2 列 | 第 3 列 | 第 4 列 | 要求 |
|---|---|---|---|---|---|
| 第 1 行 | 0 | 0 | 0 | 0 | 全白 |
| 第 2 行 | 0 | 1 | 1 | 0 | 中间两格黑 |
| 第 3 行 | 0 | 1 | 1 | 0 | 中间两格黑 |
| 第 4 行 | 0 | 0 | 0 | 0 | 全白 |
string pat[4] = {"0000", "0110", "0110", "0000"};然后比对新窗口时直接用字符串逐行比较。比手写 16 个 if 条件可靠得多,也不容易写错某一位。这是窗口枚举最容易出错的地方,我们把它讲清楚。
| 窗口尺寸 | 左上角最大行下标 | 循环写法 |
|---|---|---|
| 4 行 | n − 4 | i + 4 <= n 或 i <= n - 4 |
| 2 行 | n − 2 | i + 2 <= n |
| 1 行 | n − 1 | i + 1 <= n(即 i < n) |
左上角在第 i 行时,窗口占 i、i+1、i+2、i+3 共 4 行
要求 i + 3 ≤ n − 1,即 i ≤ n − 4
所以写作 i + 4 <= n
写成 i < n − 3,会让 i 最大取到 n − 4(看似对)
但写成 i < n − 4 就会漏掉最后一个位置
写成 i <= n 会越界访问
⚠️ 建议统一用 i + 4 <= n 的形式
for (int i = 0; i + 3 < n; i++)——因为窗口右下角行号是 i + 3,直接写 i + 3 < n 与访问形式对应,一眼就能看出不会越界。把 4 行图案写成字符串数组,逐行比较
直接写 if 判断每一格的颜色
| 方案 | 代码量 | 出错概率 |
|---|---|---|
| 模板数组 | 约 12 行 | 低 |
| 手写条件 | 约 30 行 | 中高 |
第一行输入 t,随后每组先一行 n m,再 n 行 01 串。程序会搜索目标 4×4 花纹。
点按钮开始 →
#include <bits/stdc++.h> using namespace std; // 目标花纹(0 白 1 黑) string pat[4] = {"0000", "0110", "0110", "0000"}; int main() { int t; scanf("%d", &t); while (t--) { int n, m; scanf("%d %d", &n, &m); vector<string> g(n); for (int i = 0; i < n; i++) cin >> g[i]; bool found = false; // 枚举 4×4 窗口的左上角 for (int i = 0; i + 3 < n && !found; i++) { for (int j = 0; j + 3 < m && !found; j++) { bool ok = true; for (int r = 0; r < 4 && ok; r++) { for (int c = 0; c < 4; c++) { if (g[i + r][j + c] != pat[r][c]) { ok = false; break; } } } if (ok) found = true; } } printf("%s\n", found ? "Yes" : "No"); } return 0; }
g[i+r][j+c] != pat[r][c] 这种"行列对应"的比对非常直观,而且以后要改花纹(比如换成 5 × 5 图案)只需改 pat 的定义,循环结构完全不用动。| 代码 | 作用 | 为什么这样写 |
|---|---|---|
i + 3 < n | 保证窗口不越界 | 右下角行号是 i+3,与访问形式对应 |
for (r = 0; r < 4 && ok; r++) | 逐行比对 | 加上 ok 条件可提前跳出 |
g[i+r][j+c] != pat[r][c] | 逐格比对 | 统一用相对偏移,避免手写下标 |
found ? "Yes" : "No" | 输出 | 三目运算符一行搞定 |
i < n - 4,漏掉最后一个候选位置;② 模板某一位写错(比如把第 2 行写成 1001);③ 多组测试时 found 没在每组开头重置。写完程序后,用这些数据自查一遍:
| 输入 | 答案 | 考察点 |
|---|---|---|
1 | No | 题面样例 1:行数不足 4 |
1 | Yes | 题面样例 2 |
1 | No | 题面样例 3 |
1 | Yes | 恰好是目标花纹 |
1 | No | 四行都是 0110,不满足 |
2 | Yes No | 多组测试,考察状态重置 |
i <= n - 4 或 i + 4 <= n 才对。0110,不是 1001 也不是 0111。需要存每个测试用例的网格。
✅ 最多约 160 万次字符比较,瞬间完成。
// 固定尺寸窗口的通用枚举模板 int WH = 4, WW = 4; // 窗口高、宽 for (int i = 0; i + WH - 1 < n; i++) { for (int j = 0; j + WW - 1 < m; j++) { // 处理窗口 (i, j) 到 (i+WH-1, j+WW-1) } } // 注意:i + WH - 1 < n 等价于 i + WH <= n 等价于 i <= n - WH // 用 vector<string> 存网格,便于按字符访问 vector<string> g(n); for (int i = 0; i < n; i++) cin >> g[i]; g[i][j] 就是第 i 行第 j 列的字符 // 模板匹配的通用写法 bool match(int i, int j, const vector<string> &pat) { for (int r = 0; r < (int)pat.size(); r++) for (int c = 0; c < (int)pat[0].size(); c++) if (g[i+r][j+c] != pat[r][c]) return false; return true; }
把这道题用到的基本功拆出来,它们能迁移到很多同类问题上。
| 能力点 | 本题怎么用 | 还能迁移到 |
|---|---|---|
| 固定窗口枚举 | 上界写作 i + W − 1 < n | 所有模板匹配题 |
| 模板数组 | 把图案写成常量 | 图像识别、棋盘花纹、模式检测 |
| 多组测试重置 | 每组开头重置状态变量 | 所有含 t 组测试的题目 |
? 表示通配,比对时遇到 pat[r][c] == '?' 就跳过。这是模式匹配中"通配符"的最朴素实现。)