202409-黑白方块(luogu-B4040)

GESP C++四级2024年9月真题。本题主要考察二维数组的应用。暴力难度不大，整体难度⭐⭐★☆☆。本题在洛谷评定为普及-。

luogu-B4040 [GESP202409 四级] 黑白方块

题目要求

题目描述

小杨有一个 $n$ 行 $m$ 列的网格图，其中每个格子要么是白色，要么是黑色。小杨想知道网格图中是否存在一个满足如下条件的子矩形：
子矩形由 $4$ 行 $4$ 列组成；
子矩形的第 $1$ 行和第 $4$ 行只包含白色格子；
对于子矩形的第 $2$ 行和第 $3$ 行，只有第 $1$ 个和第 $4$ 个格子是白色的，其余格子都是黑色的；
请你编写程序帮助小杨判断。

输入格式

第一行包含一个正整数 $t$ ，代表测试用例组数。
接下来是 $t$ 组测试用例。对于每组测试用例，一共 $n+1$ 行。
第一行包含两个正整数 $n,m$ ，含义如题面所示。
之后 $n$ 行，每行一个长度为 $m$ 的 $01$ 串，代表网格图第 $i$ 行格子的颜色，如果为 $0$ ，则对应格子为白色，否则为黑色。

输出格式

对于每组测试用例，如果存在，输出 Yes，否则输出 No。

输入输出样例 #1

输入 #1

输出 #1

No
Yes
No

说明/提示

样例 1 解释

数据规模与约定

对全部的测试数据，保证 $1 \leq t\leq 10$ ， $1 \leq n,m \leq 100$ 。

题目分析

本题的解题思路如下：

题目要求在一个 $n$ 行 $m$ 列的网格中，找到一个满足特定条件的 $4\times4$ 子矩阵。具体要求是：
- 第 $1$ 行和第 $4$ 行全为白色（ $0$ ）
- 第 $2$ 行和第 $3$ 行只有第 $1$ 列和第 $4$ 列是白色（ $0$ ），中间两列是黑色（ $1$ ）
解题关键点：
- 子矩阵大小固定为 $4\times4$ ，不需要考虑其他尺寸
- 只需要判断是否存在这样的子矩阵，不需要统计数量
- 可以使用暴力枚举方法，遍历所有可能的左上角位置
具体实现步骤：
- 读入网格数据，用字符串数组存储
- 遍历所有可能的左上角位置 $(i,j)$
- 对每个位置，检查以 $(i,j)$ 为左上角的 $4\times4$ 子矩阵是否满足要求
- 如果找到一个满足要求的子矩阵，输出 “Yes” 并结束
- 如果遍历完所有位置都没找到，输出 “No”
时间复杂度分析：
- 对于每个测试用例，需要遍历所有可能的左上角位置： $O(nm)$
- 对每个位置，需要检查 $4\times4$ 的子矩阵： $O(16)$
- 总时间复杂度： $O(nm)$
- 由于 $n,m\leq100$ ，暴力方法完全可以通过
注意事项：
- 检查子矩阵时要注意边界条件，防止越界
- 字符串中 ‘ $0$ ’ 表示白色，’ $1$ ’ 表示黑色，要用字符比较而不是数字比较

这道题目虽然看起来有点复杂，但实际上是一道比较直观的模拟题，主要考察细心和代码实现能力。只要按照题目要求仔细检查每个位置的子矩阵是否符合条件即可。

示例代码

#include <iostream>
#include <string>

// 存储输入的网格图，每个字符串表示一行，'0'表示白色，'1'表示黑色
std::string str_ary[105];

/**
 * 检查从(x,y)位置开始的4x4子矩阵是否满足题目要求
 * @param x 子矩阵左上角的行坐标
 * @param y 子矩阵左上角的列坐标
 * @param n 网格总行数
 * @param m 网格总列数
 * @return 是否满足要求
 */
bool check(int x, int y, int n, int m) {
    // 首先检查是否越界
    if (x + 4 > n || y + 4 > m) {
        return false;
    }
    
    // 遍历4x4子矩阵的每个位置
    for (int i = x; i < x + 4; i++) {
        for (int j = y; j < y + 4; j++) {
            // 检查第1行和第4行是否全为白色(0)
            if (i == x || i == x + 3) {
                if (str_ary[i][j] != '0') {
                    return false;
                }
            }
            
            // 检查第2行和第3行的第1列和第4列是否为白色(0)
            if (j == y || j == y + 3) {
                if (str_ary[i][j] != '0') {
                    return false;
                }
            }
            
            // 检查第2行和第3行的中间两列是否为黑色(1)
            if ((i == x + 1 || i == x + 2) && (j == y + 1 || j == y + 2)) {
                if (str_ary[i][j] != '1') {
                    return false;
                }
            }
        }
    }
    return true;
}

int main() {
    // 读取测试用例数量
    int t;
    std::cin >> t;
    
    // 处理每个测试用例
    while (t--) {
        // 读取网格的行数和列数
        int n, m;
        std::cin >> n >> m;
        
        // 读入网格数据
        for (int i = 0; i < n; i++) {
            std::cin >> str_ary[i];
        }
        
        // 标记是否找到符合要求的子矩阵
        bool flag = false;
        
        // 枚举所有可能的左上角起点
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                // 检查以(i,j)为左上角的4x4子矩阵是否符合要求
                if (check(i, j, n, m)) {
                    std::cout << "Yes" << std::endl;
                    flag = true;
                    break;
                }
            }
            if (flag) {
                break;
            }
        }
        
        // 如果没有找到符合要求的子矩阵，输出No
        if (!flag) {
            std::cout << "No" << std::endl;
        }
    }
    return 0;
}

本文由coderli.com原创，按照CC BY-NC-SA 4.0 进行授权
所有代码已上传至Github：https://github.com/lihongzheshuai/yummy-code
“luogu-”系列题目可在 洛谷题库 在线评测。
“bcqm-”系列题目可在 编程启蒙题库 在线评测。

GESP/CSP 认证学习微信公众号

最后更新于 2025年9月15日

202406-宝箱(luogu-B4006)202409-区间排序(luogu-B4041)