GESP 题解库 / 4 级题解 / [GESP202406 四级] 黑白方块 · 第 13 / 25 题
GESP202406 四级 · B4005 · 简单

平衡子矩形

求最大的子矩形,使其中黑白格子数量相同,输出格子数;不存在则输出 0。

📊
n, m ≤ 10
网格规模
🔢
int
数值类型
⚡
O(n²m²)
时间复杂度
🎯
0→−1 转化 + 前缀和
核心算法
01
题目拆解
把题目拆成一块块,看清全貌

📝 题目原文

给定 n 行 m 列的 01 网格(0 白、1 黑)。若一个子矩形中黑色格子与白色格子数量相同,则称它是平衡的。

求最大的平衡子矩形包含多少个格子;若不存在则输出 0。

💡
人话翻译:找一个子矩形,里面 0 和 1 一样多。关键技巧是把 0 换成 −1,这样"数量相同"就变成了"和为 0",然后就能用前缀和快速判断了。

🔍 关键词提取

0 / 1 转换二维前缀和和为 0四重循环枚举

已知条件

项目说明
输入第一行 n、m;随后 n 行 01 串
输出最大平衡子矩形的格子数,无解输出 0
数据范围1 ≤ n, m ≤ 10
编码0 = 白色,1 = 黑色
平衡条件黑格数 == 白格数

需要解决的问题

02
思维导图
整理解题思路的全貌
⚖️ 0→−1,把平衡变成和为 0
🧠 核心转化
0 记作 −1
1 记作 +1
黑白相等 ⇒ 总和为 0
把计数问题变成求和问题
📊 前缀和
二维前缀和 pre[][]
矩形和 O(1) 查询
只需判断是否为 0
n, m ≤ 10 甚至可暴力
🔍 枚举矩形
四重循环:上下左右边界
面积 = 行数 × 列数
和为 0 就更新答案
注意无解输出 0
⚠️ 易错点
忘了 0 要转 −1
答案记录的是格子数不是和
无解时输出 0
面积计算漏 +1
03
样例手算推导
样例 4×5 网格的最优矩形

🧮 样例:答案 16

00000
01111
00011
00011
1
第 1 步:先把 0 换成 −1

原网格:00000 / 01111 / 00011 / 00011

转换后:−1 −1 −1 −1 −1

−1 +1 +1 +1 +1

−1 −1 −1 +1 +1

−1 −1 −1 +1 +1

转换完成

2
第 2 步:试整个网格(4×5 = 20 格)

总和 = −5 + 1 + 0 + 0 = −4

不为 0 → 不平衡

(也可以直接数:白 12 个、黑 8 个,确实不等)

❌ 20 格不行

3
第 3 步:试第 1~4 行、第 2~5 列(4×4 = 16 格)

取出的部分:0000 / 1111 / 0011 / 0011

白格数:4 + 0 + 2 + 2 = 8

黑格数:0 + 4 + 2 + 2 = 8

相等 → 平衡

✅ 16 格,是候选答案

4
第 4 步:还有更大的吗?

总格子数 20,比 16 大的只有 20(已排除)、18、17

18 格需要 3×6 或 6×3,但网格只有 4 行 5 列,不成立

17 格不是任何矩形的面积(矩形面积必为行数×列数)

所以 16 就是最大

✅ 输出 16

答案 16 ✓

🔑
注意:答案是"格子数",不是"和"!前缀和在这里只用来判断是否平衡(和为 0),真正要输出的是矩形面积 = (r2−r1+1) × (c2−c1+1)。这两个概念千万不要混。

🧮 什么时候输出 0

如果整个网格中找不到任何平衡子矩形,就要输出 0。

数据分析答案
1 1 / 1只有一个黑格,但单个格子的面积是奇数,不可能黑白相等0
1 1 / 0只有一个白格,同理0
2 1 / 1 / 12 个黑格,白 0 个,不相等0
1 2 / 1 0一个黑一个白,相等 → 2 格2
2 2 / 0 1 / 1 0两个 0、两个 1 → 4 格4
⚠️
一个重要观察:平衡要求黑格数 = 白格数,所以总面积一定是偶数。如果整个网格总格数是奇数,那就必须先排除"整个网格"这个候选,继续找更小的偶数面积矩形。没有任何候选时,按要求输出 0。
04
解法对比
0→−1 转化 vs 直接数数量

⚔️ 解法对比

🟢 0→−1 + 前缀和(推荐) 推荐

把 0 记作 −1,用二维前缀和判断矩形和是否为 0

  • 时间 O(n²m²)
  • 每个矩形判定 O(1)
  • 逻辑极简
  • n, m ≤ 10 更是随便过
💡
为什么推荐:"两种元素数量相等"是极其常见的题设,把其中一种映射成 −1、另一种映射成 +1,就能用"和为 0"来统一判定,这是一维和二维问题的通用技巧。

🟠 每个矩形分别数黑白个数

对每个候选矩形遍历其内部格子,分别统计 0 和 1 的个数

  • 时间 O(n²m² × nm)
  • 本题 n, m ≤ 10 也够快
  • 但代码更冗长
  • 没有体现转化技巧
⚠️
本题两者都能过:n, m ≤ 10 时最坏约 3000 × 100 = 30 万次,完全可行。但掌握 0→−1 技巧,在更大的数据范围下仍然是必需的。

📈 性能对比

方案单次判定代价可扩展性
0→−1 前缀和O(1)强(n, m 大也够)
逐格统计O(nm)弱
05
算法流程图
转换 → 前缀和 → 枚举矩形判定
开始读入 n、m 和网格;把 0 转成 −1,1 保持 +1建立二维前缀和 pre[][];ans = 0枚举上边界 r1、下边界 r2枚举左边界 c1、右边界 c2O(1) 求出该矩形之和;面积 = 行数 × 列数矩形和 == 0 吗?是 ✓ans = max(ans, 面积)否 ✗跳过输出 ans结束还有列边界组合 → 继续
← 左右滑动查看完整流程图
06
动手算一算
自己输入数据试试看

⚖️ 最大平衡子矩形查找器

第一行输入 n 和 m,随后 n 行 01 串。程序会找出黑白数量相等的最大子矩形。

结果会显示在这里

点按钮开始 →

07
代码精讲
逐段拆解,彻底搞懂

💻 完整 C++ 代码

#include <bits/stdc++.h>
using namespace std;

int a[15][15];
int pre[15][15];

int main() {
    int n, m;
    scanf("%d %d", &n, &m);

    for (int i = 1; i <= n; i++) {
        string s;
        cin >> s;
        for (int j = 1; j <= m; j++) {
            // 关键转换:0(白)记作 -1,1(黑)记作 +1
            a[i][j] = (s[j - 1] == '0') ? -1 : 1;
        }
    }

    // 二维前缀和(下标从 1 开始,省去边界特判)
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= m; j++)
            pre[i][j] = pre[i-1][j] + pre[i][j-1] - pre[i-1][j-1] + a[i][j];

    int ans = 0;
    for (int r1 = 1; r1 <= n; r1++)
        for (int r2 = r1; r2 <= n; r2++)
            for (int c1 = 1; c1 <= m; c1++)
                for (int c2 = c1; c2 <= m; c2++) {
                    // 矩形和,为 0 说明黑白数量相等
                    int sum = pre[r2][c2] - pre[r1-1][c2] - pre[r2][c1-1] + pre[r1-1][c1-1];
                    if (sum == 0) {
                        int cells = (r2 - r1 + 1) * (c2 - c1 + 1);
                        if (cells > ans) ans = cells;      // 注意记录的是面积
                    }
                }

    printf("%d\n", ans);      // 无解时 ans 保持 0,正好符合要求
    return 0;
}
🔑
为什么答案初始化为 0 就够了?因为题目要求"不存在则输出 0",而 ans 初始为 0,找不到任何平衡矩形时就自然输出 0,不需要任何额外的无解判断。这种"让初值恰好等于无解答案"的写法很省事。

📖 关键几行怎么看

代码作用为什么这样写
(s[j-1] == '0') ? -1 : 1关键转换把"数量相等"变成"和为 0"
pre[i][j] = pre[i-1][j] + pre[i][j-1] - pre[i-1][j-1] + a[i][j]二维前缀和容斥原理,下标从 1 开始可免特判
if (sum == 0)平衡判定和为 0 等价于黑白数量相等
int cells = (r2-r1+1) * (c2-c1+1);面积输出的是格子数,不是和
⚠️
三个坑:① 忘了把 0 转成 −1(那样"和为 0"就不再代表平衡);② 把 sum 当成答案输出(应该输出面积);③ 面积漏掉 +1,行数是 r2 - r1 + 1。
08
边界测试 & 易错点
把坑都踩一遍,考试不翻车

🧪 边界测试用例表

写完程序后,用这些数据自查一遍:

输入答案考察点
4 5
00000 / 01111 / 00011 / 00011
16题面样例
1 1
1
0单格无法平衡,输出 0
1 2
1 0
2一黑一白,恰好平衡
2 2
0 1 / 1 0
4两黑两白,整个网格平衡
2 2
0 0 / 0 0
0全是白格,不可能黑白相等
1 4
1 1 0 0
4两黑两白,整行平衡
✅
自查清单:① 做了 0→−1 转换吗?② 输出的意思是格子数吗?③ 无解时输出 0 吗?

🚨 易错点清单

⚠️
忘记 0→−1 转换:那样和 == 0就不代表黑白相等了,必须做映射。
⚠️
把和当答案:是要输出格子数,而平衡时和恰好是 0,直接输出会全错。
⚠️
面积漏 +1:行数 = r2 − r1 + 1,列数 = c2 − c1 + 1。
09
复杂度分析
算算效率怎么样

📊 复杂度四宫格

时间复杂度
O(n²m²)
空间复杂度
O(nm)
n, m 最大
10
最坏运算
约 3000 次判定

时间怎么算的?

空间都用在哪?

需要存网格和前缀和,各 10 × 10。

✅ 约 3000 次判定,任何语言瞬间完成。n, m ≤ 10 这个范围本身就在提示:暴力枚举即可。

10
知识拓展
学一道题,会一类题

🔗 常用技巧小抄

// "数量相等" 类问题的通用转换技巧
// 两种状态 -> 分别映射为 +1 / -1
// "两者数量相等" <=> "区间和为 0"
// 例如:黑白相等、AB 数量相等、+/- 抵消、括号匹配

// 二维前缀和(下标从 1 开始)
long long pre[15][15];
for (int i = 1; i <= n; i++)
    for (int j = 1; j <= m; j++)
        pre[i][j] = pre[i-1][j] + pre[i][j-1] - pre[i-1][j-1] + a[i][j];

// 矩形和
long long rectSum(int r1, int c1, int r2, int c2) {
    return pre[r2][c2] - pre[r1-1][c2] - pre[r2][c1-1] + pre[r1-1][c1-1];
}

// 一维版本:求最长的"0/1 数量相等"的子数组
// 也完全一样:把 1 记作 +1、0 记作 -1,找前缀和相等的最远两点

🌟 举一反三

把这道题用到的基本功拆出来,它们能迁移到很多同类问题上。

能力点本题怎么用还能迁移到
数量相等 → 和为 0+1 / −1 映射括号匹配、黑白平衡、抵消计分
二维前缀和O(1) 矩形求和子矩阵统计、图像分析
暴力枚举边界四重循环小规模网格的最优子矩形问题
🌟
思考题:如果数据范围放大到 n, m ≤ 500,四重循环就不够了(O(n²m²) 会超时)。该怎么优化?(提示:固定上下两行 r1、r2,把每一列在这两行之间的和压成一个数,问题就变成一维的"找和为 0 的最长子数组",可以用前缀和 + 哈希表在线性时间内解决,整体降到 O(n²m)。这是"最大子矩阵"类问题的经典降维套路。)