GESP 题解库 / 4 级题解 / [GESP202409 四级] 黑白方块 · 第 11 / 25 题
GESP202409 四级 · B4040 · 简单

黑白方块

判断网格中是否存在满足特定花纹的 4 × 4 子矩形。

📊
n, m ≤ 100
网格规模
🔢
t ≤ 10
测试组数
⚡
O(nm × 16)
时间复杂度
🎯
模板比对
核心算法
01
题目拆解
把题目拆成一块块,看清全貌

📝 题目原文

网格中每格是黑或白。请判断是否存在一个 4 行 4 列的子矩形,满足:

输入中 0 表示白色、1 表示黑色。存在输出 Yes,否则输出 No。

💡
人话翻译:要找一个长这样的 4 × 4 花纹:

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 列

需要解决的问题

02
思维导图
整理解题思路的全貌
🔍 写死模板 + 逐格比对
📥 读入
t 组测试
每组 n、m
n 行 01 串
注意多组要重置状态
📐 目标模板
第 1 行 0000
第 2 行 0110
第 3 行 0110
第 4 行 0000
🔍 枚举比对
左上角 (i, j) 从 0 到 n−4、m−4
逐格与模板比较
全部相同 → Yes
找到即可 break
⚠️ 易错点
循环上界写成 i < n−3(漏一个)
模板写错一位
多组数据忘记重置 found
n < 4 或 m < 4 时直接 No
03
样例手算推导
三个样例的判定过程

🧮 样例逐组分析

样例答案依次是 No、Yes、No。

1
第 1 组:n = 1, m = 4

只有 1 行,而图案需要 4 行

根本没有 4 × 4 的子矩形

❌ No(尺寸不够)

2
第 2 组:5 × 5

网格中第 1~4 行、第 1~4 列恰好是:

0000(第 1 行)

0110(第 2 行)

0110(第 3 行)

0000(第 4 行)

与目标模板逐格一致

✅ Yes

3
第 3 组:5 × 5

网格为 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 行0000全白
第 2 行0110中间两格黑
第 3 行0110中间两格黑
第 4 行0000全白
🔑
最稳妥的做法是把这个模板写成常量数组:string pat[4] = {"0000", "0110", "0110", "0000"};然后比对新窗口时直接用字符串逐行比较。比手写 16 个 if 条件可靠得多,也不容易写错某一位。

🧮 循环上界为什么要 − 4 + 1?

这是窗口枚举最容易出错的地方,我们把它讲清楚。

窗口尺寸左上角最大行下标循环写法
4 行n − 4i + 4 <= n 或 i <= n - 4
2 行n − 2i + 2 <= n
1 行n − 1i + 1 <= n(即 i < n)
1
直观理解

左上角在第 i 行时,窗口占 i、i+1、i+2、i+3 共 4 行

要求 i + 3 ≤ n − 1,即 i ≤ n − 4

所以写作 i + 4 <= n

2
常见错误

写成 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 与访问形式对应,一眼就能看出不会越界。
04
解法对比
模板数组比对 vs 手写 if

⚔️ 解法对比

🟢 模板数组逐格比对(推荐) 推荐

把 4 行图案写成字符串数组,逐行比较

  • 时间 O(nm × 16)
  • 代码 12 行
  • 模板一目了然
  • 改需求只需改模板
💡
为什么推荐:代码里直接能看到目标长相,评审或自查时非常直观;也不容易发生"手写 16 个条件漏一个"的错误。

🟠 手写 16 个条件判断

直接写 if 判断每一格的颜色

  • 代码冗长
  • 容易写错某一位
  • 可读性差
  • 功能上等价
⚠️
注意:如果题目给的花纹很复杂(比如 10 × 10),手写条件完全不可行,模板比对才是通用做法。

📈 性能对比

方案代码量出错概率
模板数组约 12 行低
手写条件约 30 行中高
05
算法流程图
枚举左上角并逐格比对模板
开始读入 t;定义目标模板 pat[4]处理每一组测试数据读入 n、m 和网格;found = false枚举左上角 (i, j):i 从 0 到 n−4,j 从 0 到 m−4逐格比对 4×4 区域与模板是否完全一致?是 ✓found = true,跳出否 ✗继续下一个位置输出 found ? Yes : No结束还有测试组 → 继续
← 左右滑动查看完整流程图
06
动手算一算
自己输入数据试试看

🔍 目标花纹检测器

第一行输入 t,随后每组先一行 n m,再 n 行 01 串。程序会搜索目标 4×4 花纹。

结果会显示在这里

点按钮开始 →

07
代码精讲
逐段拆解,彻底搞懂

💻 完整 C++ 代码

#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 没在每组开头重置。
08
边界测试 & 易错点
把坑都踩一遍,考试不翻车

🧪 边界测试用例表

写完程序后,用这些数据自查一遍:

输入答案考察点
1
1 4
0110
No题面样例 1:行数不足 4
1
5 5
00000 / 01100 / 01100 / 00001 / 01100
Yes题面样例 2
1
5 5
00000 / 01100 / 01110 / 00001 / 01100
No题面样例 3
1
4 4
0000 / 0110 / 0110 / 0000
Yes恰好是目标花纹
1
4 4
0110 / 0110 / 0110 / 0110
No四行都是 0110,不满足
2
4 4
0000 / 0110 / 0110 / 0000
4 4
0110 / 0110 / 0110 / 0110
Yes
No
多组测试,考察状态重置
✅
自查清单:① 循环上界对吗?② 模板四位都对吗?③ 每组都重置 found 了吗?

🚨 易错点清单

⚠️
循环上界错:左上角行下标最大是 n − 4,写成 i <= n - 4 或 i + 4 <= n 才对。
⚠️
模板写错一位:目标花纹的第 2、3 行是 0110,不是 1001 也不是 0111。
⚠️
多组数据没重置 found:上一组找到过就会污染下一组的结果。
09
复杂度分析
算算效率怎么样

📊 复杂度四宫格

时间复杂度
O(t × n × m × 16)
空间复杂度
O(n × m)
n, m 最大
100
最坏运算
约 1.6 × 10⁶

时间怎么算的?

空间都用在哪?

需要存每个测试用例的网格。

✅ 最多约 160 万次字符比较,瞬间完成。

10
知识拓展
学一道题,会一类题

🔗 常用技巧小抄

// 固定尺寸窗口的通用枚举模板
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 组测试的题目
🌟
思考题:如果题目把花纹改成"第 1 行全白、第 2 行中间两格黑、第 3 行可以任意",该怎么在模板比对里表达"任意"?(提示:用特殊字符 ? 表示通配,比对时遇到 pat[r][c] == '?' 就跳过。这是模式匹配中"通配符"的最朴素实现。)