【GESP】C++四级真题 luogu-B4040 [GESP202409 四级] 黑白方块

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

3
1 4
0110
5 5
00000
01100
01100
00001
01100
5 5
00000
01100
01110
00001
01100

输出 #1

No
Yes
No

说明/提示

样例 1 解释

0000
0110
0110
0000

数据规模与约定

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

---

题目分析

本题的解题思路如下：

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

---

所有代码已上传至Github：https://github.com/lihongzheshuai/yummy-code

GESP 学习专题站：GESP WIKI

“luogu-”系列题目可在洛谷题库进行在线评测。

“bcqm-”系列题目可在编程启蒙题库进行在线评测。

欢迎加入：Java、C++、Python技术交流QQ群(982860385)，大佬免费带队，有问必答

欢迎加入：C++ GESP/CSP认证学习QQ频道，考试资源总结汇总

欢迎加入：C++ GESP/CSP学习交流QQ群(688906745)，考试认证学员交流，互帮互助

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