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

GESP C++四级2024年6月真题。本题主要考察二维数组，多重循环操作甚至前缀和思想。暴力难度不大，前缀和优化需要点思想，整体难度⭐⭐★☆☆。本题在洛谷评定为普及-。

luogu-B4005 [GESP202406 四级] 黑白方块

题目要求

题目描述

小杨有一个 $n$ 行 $m$ 列的网格图，其中每个格子要么是白色，要么是黑色。对于网格图中的一个子矩形，小杨认为它是平衡的当且仅当其中黑色格子与白色格子数量相同。小杨想知道最大的平衡子矩形包含了多少个格子。

输入格式

第一行包含两个正整数 $n,m$，含义如题面所示。

之后 $n$ 行，每行一个长度为 $m$ 的 $01$ 串，代表网格图第 $i$ 行格子的颜色，如果为 $0$，则对应格子为白色，否则为黑色。

输出格式

输出一个整数，代表最大的平衡子矩形包含格子的数量，如果不存在则输出 $0$。

输入输出样例 #1

输入 #1

4 5
00000
01111
00011
00011

输出 #1

16

说明/提示

【样例解释】:

对于样例 $1$，假设 $(i,j)$ 代表第 $i$ 行第 $j$ 列，最大的平衡子矩形的四个顶点分别为 $(1,2),(1,5),(4,2),(4,5)$。

【数据范围】:

对于全部数据，保证有 $1\leq n,m\leq 10$。

---

题目分析

问题分析

• 题目要求在一个 $n \times m$ 的黑白方格矩阵中找到最大的平衡子矩形
• 平衡子矩形指黑色格子数量等于白色格子数量的矩形区域
• 需要计算这个最大平衡子矩形包含多少个格子

解题思路

方法一：暴力枚举

• 枚举所有可能的子矩形（通过左上角和右下角坐标确定），四重循环
  • 两重循环枚举所有可能的子矩形的左上角坐标 $(i,j)$
  • 两重循环枚举所有可能的子矩形的右下角坐标 $(k,l)$
• 对每个子矩形，统计其中的黑白格子数量，统计方法为：
  • 遍历子矩形内的每个格子，假设白色格子为-1，黑色格子为1
  • 统计所有格子的和，和为0的子矩形是平衡的
• 如果子矩形是平衡的，更新最大面积，面积公式为 $(k-i+1)(l-j+1)$
• 时间复杂度：$O(n^2m^2\times nm)$，需要遍历每个格子作为左上角和右下角，对每个子矩形还需要$O(nm)$的时间统计黑白格子数量，即约等于$O(n^6)$级别
• 空间复杂度：$O(nm)$，只需要存储原始矩阵

---

方法二：前缀和优化

前缀和思想：

• 将白色格子记为-1，黑色格子记为1
• 构建二维前缀和数组 $sum[i][j]$，表示从 $(1,1)$ 到 $(i,j)$ 的所有格子值之和
• 对于任意子矩形(x1,y1)到(x2,y2)，其所有格子的和可以通过前缀和快速计算： \(sum[x2][y2] - sum[x1-1][y2] - sum[x2][y1-1] + sum[x1-1][y1-1]\)
• 如果和为0，说明该子矩形是平衡的

优化后算法步骤：

• 预处理构建二维前缀和数组 $sum[i][j]$ \(sum[i][j] = sum[i-1][j] + sum[i][j-1] - sum[i-1][j-1] + ary[i][j]\)
• 枚举子矩形的左上角和右下角坐标 $(i,j)$ 和 $(k,l)$
• 使用前缀和公式$O(1)$时间计算子矩形中的黑白格子差值 \(sum[k][l] - sum[i-1][l] - sum[k][j-1] + sum[i-1][j-1]\)
• 如果差值为0，计算面积并更新最大值

时间复杂度分析：

• 构建前缀和数组需要$O(nm)$
• 枚举所有可能的子矩形需要$O(n^2m^2)$
• 计算每个子矩形的和只需要$O(1)$
• 总时间复杂度为$O(n^2m^2)$, 即约为$O(n^4)$级别

空间复杂度分析：

• 需要额外的二维数组存储前缀和
• 空间复杂度为$O(nm)$

前缀和方法有效的降低了时间复杂度，将原本的$O(n^6)$优化为$O(n^4)$级别。

---

示例代码

方法一、暴力循环

#include <cmath>
#include <iostream>
#include <string>

// 存储黑白方块矩阵，-1表示白色，1表示黑色
int ary[15][15];
// 存储前缀和数组
int sum[15][15];

// 检查指定矩形区域内黑白方块是否平衡
// 参数：f_row,f_col 左上角坐标，l_row,l_col 右下角坐标
bool check(int f_row, int f_col, int l_row, int l_col) {
    int sum = 0;
    // 遍历矩形区域
    for (int i = f_row; i <= l_row; i++) {
        for (int j = f_col; j <= l_col; j++) {
            sum += ary[i][j];
        }
    }
    // 如果和为0，说明黑白方块数量相等
    return sum == 0 ? true : false;
}

int main() {
    // 读入矩阵大小
    int n, m;
    std::cin >> n >> m;

    // 读入矩阵数据并计算前缀和
    for (int i = 1; i <= n; i++) {
        std::string r_str;
        std::cin >> r_str;
        for (int j = 1; j <= m; j++) {
            // 将0转换为-1(白色)，1保持不变(黑色)
            ary[i][j] = r_str[j - 1] == '0' ? -1 : 1;
            // 计算二维前缀和
            sum[i][j] =
                sum[i - 1][j] + sum[i][j - 1] - sum[i - 1][j - 1] + ary[i][j];
        }
    }

    // 枚举所有可能的矩形区域
    int max_area = 0;
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            for (int k = i; k <= n; k++) {
                for (int l = j; l <= m; l++) {
                    // 检查当前矩形是否平衡
                    if (check(i, j, k, l)) {
                        // 计算矩形面积并更新最大值
                        int area = (k - i + 1) * (l - j + 1);
                        max_area = std::max(max_area, area);
                    }
                }
            }
        }
    }
    // 输出结果
    std::cout << max_area;
    return 0;
}

方法二、前缀和优化

#include <cmath>
#include <iostream>
#include <string>

// 存储黑白方块矩阵，-1表示白色，1表示黑色
int ary[15][15];
// 存储二维前缀和数组
int sum[15][15];
int main() {
    // 读入矩阵大小n行m列
    int n, m;
    std::cin >> n >> m;

    // 读入矩阵数据并计算前缀和
    for (int i = 1; i <= n; i++) {
        std::string r_str;
        std::cin >> r_str;
        for (int j = 1; j <= m; j++) {
            // 将0转换为-1(白色)，1保持不变(黑色)
            ary[i][j] = r_str[j - 1] == '0' ? -1 : 1;
            // 计算二维前缀和
            sum[i][j] =
                sum[i - 1][j] + sum[i][j - 1] - sum[i - 1][j - 1] + ary[i][j];
        }
    }
    // 记录最大平衡矩形面积
    int max_area = 0;
    // 枚举所有可能的矩形区域
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            for (int k = i; k <= n; k++) {
                for (int l = j; l <= m; l++) {
                    // 使用前缀和计算当前矩形区域内的黑白方块差值
                    int area_sum = sum[k][l] - sum[i - 1][l] - sum[k][j - 1] +
                                   sum[i - 1][j - 1];
                    // 如果差值为0，说明黑白方块数量相等
                    if (area_sum == 0) {
                        // 计算当前平衡矩形的面积
                        int area = (k - i + 1) * (l - j + 1);
                        // 更新最大面积
                        max_area = std::max(max_area, area);
                    }
                }
            }
        }
    }
    // 输出结果
    std::cout << max_area;
    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 认证学习微信公众号