黑白方块 题解

题目分析

我们需要在一个 n × m 的 01 网格中，找出是否存在一个特定的 4 × 4 子矩形。这个子矩形的形状是固定的，就像题目提示中给出的那样：

0000
0110
0110
0000

其中 0 表示白色格子，1 表示黑色格子。也就是说，如果要找到这样一个子矩形，必须满足：

• 第 1 行全部是 0（白色）；
• 第 1 列和第 4 列在 4 行中都是 0（白色）；
• 第 2 行、第 3 行的第 2 列和第 3 列必须是 1（黑色）。

由于数据范围很小（n, m ≤ 100，且测试用例组数 t ≤ 10），我们可以直接枚举所有可能的 4 × 4 子矩形，逐一检查是否符合上述模式。

解题思路

最直观的做法是模拟：

1. 把目标图案存成一个模板 match[4][4]。
2. 读入整个网格 w，用二维数组存储每个格子的值（0 或 1）。
3. 枚举子矩形左上角的坐标 (i, j)，其中 1 ≤ i ≤ n-3，1 ≤ j ≤ m-3。
4. 对于每个候选位置，将对应的 4 × 4 区域与 match 对比，完全一致则标记为找到。
5. 根据是否找到输出 "Yes" 或 "No"。

算法说明

我们可以用两层循环枚举所有可能的左上角，对每个左上角调用检查函数。检查函数逐个格子比较，只要发现一个不匹配就返回 false。

为了提高可读性，我们直接将目标模板硬编码为二维数组：

match = {
  {0, 0, 0, 0},
  {0, 1, 1, 0},
  {0, 1, 1, 0},
  {0, 0, 0, 0}
}

在 C++ 中，全局数组默认初始化为 0，因此只需把中间黑色的四个位置置为 1 即可。参考代码中的写法正是利用了这一点：先默认全 0，再设 match[1][1], match[1][2], match[2][1], match[2][2] 为 1。

时间复杂度分析

对于每组测试用例：

• 枚举左上角：(n-3) × (m-3) 种可能，近似 O(n×m)。
• 每次检查 16 个格子，常数时间。
  总体复杂度约为 O(t × n × m)。在 n, m ≤ 100, t ≤ 10 的情况下，运算次数不超过 10 × 100 × 100 × 16 = 1.6×10^6，完全可以在 1 秒内完成。

参考代码

代码使用了 1 基索引存储网格，便于和生活中的行列对应。读者在阅读时，注意字符串下标与数组索引的转换。

cpp
复制
1#include <bits/stdc++.h>
2using namespace std;
3
4const int N = 110;
5int w[N][N];          // 网格
6int n, m;
7int match[4][4];      // 目标模板
8
9// 检查以 (xa, ya) 为左上角的 4×4 区域是否匹配模板
10bool check(int xa, int ya) {
11    for (int i = 0; i < 4; i++) {
12        for (int j = 0; j < 4; j++) {
13            if (w[xa + i][ya + j] != match[i][j]) {
14                return false;
15            }
16        }
17    }
18    return true;
19}
20
21int main() {
22    // 构建目标模板，match 全局默认全 0
23    for (int i = 1; i < 3; i++) {
24        match[1][i] = match[2][i] = 1; // 设置中间黑色的四个位置
25    }
26
27    int t;
28    cin >> t;
29    while (t--) {
30        cin >> n >> m;
31        // 读入网格，转换为整数
32        for (int i = 1; i <= n; i++) {
33            string s;
34            cin >> s;
35            for (int j = 1; j <= m; j++) {
36                w[i][j] = s[j - 1] - '0';
37            }
38        }
39
40        bool found = false;
41        // 枚举所有可能的左上角
42        for (int i = 1; i <= n - 3; i++) {
43            for (int j = 1; j <= m - 3; j++) {
44                if (check(i, j)) {
45                    found = true;
46                }
47            }
48        }
49
50        if (found)
51            cout << "Yes\n";
52        else
53            cout << "No\n";
54    }
55    return 0;
56}

代码解释

1. 目标模板初始化
   全局数组 match[4][4] 未显式赋值时，所有元素默认为 0。接着用循环 for (int i = 1; i < 3; i++) 将第 1 行和第 2 行的第 1、2 列（即中间 4 个格子）设为 1。最终 match 即为要求的图案。

2. 网格读入
   每一行用一个字符串读入，字符 '0' 或 '1' 减去字符 '0' 得到整型 0 或 1，存入 w 数组。这样可以直接与模板比较。

3. 枚举与检查
   左上角 (i, j) 的行列范围保证 i+3 ≤ n 且 j+3 ≤ m，循环边界分别为 n-3 和 m-3。check 函数中，双层循环遍历这个 4×4 区域，与 match 逐元素比较，一旦某处不同立即返回 false；若全部一致则返回 true。

4. 输出
   用布尔变量 found 记录是否至少找到一处匹配。最后输出 "Yes" 或 "No"。

这道题是一道典型的模拟题，适合用来练习二维数组的遍历和匹配。只要细心实现，注意边界和下标转换，就可以顺利通过。