202406-黑白方块(luogu-B4005)

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

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

题目要求

题目描述

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

输入格式

第一行包含两个正整数 $n,m$ ，含义如题面所示。
之后 $n$ 行，每行一个长度为 $m$ 的 $01$ 串，代表网格图第 $i$ 行格子的颜色，如果为 $0$ ，则对应格子为白色，否则为黑色。

输出格式

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

输入输出样例 #1

输入 #1

输出 #1

说明/提示

【样例解释】:

对于样例 $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;
}

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

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

最后更新于 2025年9月5日

202403-做题(luogu-B3959)202406-宝箱(luogu-B4006)