求最大的子矩形,使其中黑白格子数量相同,输出格子数;不存在则输出 0。
给定 n 行 m 列的 01 网格(0 白、1 黑)。若一个子矩形中黑色格子与白色格子数量相同,则称它是平衡的。
求最大的平衡子矩形包含多少个格子;若不存在则输出 0。
0 / 1 转换二维前缀和和为 0四重循环枚举
| 项目 | 说明 |
|---|---|
| 输入 | 第一行 n、m;随后 n 行 01 串 |
| 输出 | 最大平衡子矩形的格子数,无解输出 0 |
| 数据范围 | 1 ≤ n, m ≤ 10 |
| 编码 | 0 = 白色,1 = 黑色 |
| 平衡条件 | 黑格数 == 白格数 |
00000 01111 00011 00011
原网格:00000 / 01111 / 00011 / 00011
转换后:−1 −1 −1 −1 −1
−1 +1 +1 +1 +1
−1 −1 −1 +1 +1
−1 −1 −1 +1 +1
转换完成
总和 = −5 + 1 + 0 + 0 = −4
不为 0 → 不平衡
(也可以直接数:白 12 个、黑 8 个,确实不等)
❌ 20 格不行
取出的部分:0000 / 1111 / 0011 / 0011
白格数:4 + 0 + 2 + 2 = 8
黑格数:0 + 4 + 2 + 2 = 8
相等 → 平衡
✅ 16 格,是候选答案
总格子数 20,比 16 大的只有 20(已排除)、18、17
18 格需要 3×6 或 6×3,但网格只有 4 行 5 列,不成立
17 格不是任何矩形的面积(矩形面积必为行数×列数)
所以 16 就是最大
✅ 输出 16
答案 16 ✓
如果整个网格中找不到任何平衡子矩形,就要输出 0。
| 数据 | 分析 | 答案 |
|---|---|---|
1 1 / 1 | 只有一个黑格,但单个格子的面积是奇数,不可能黑白相等 | 0 |
1 1 / 0 | 只有一个白格,同理 | 0 |
2 1 / 1 / 1 | 2 个黑格,白 0 个,不相等 | 0 |
1 2 / 1 0 | 一个黑一个白,相等 → 2 格 | 2 |
2 2 / 0 1 / 1 0 | 两个 0、两个 1 → 4 格 | 4 |
把 0 记作 −1,用二维前缀和判断矩形和是否为 0
对每个候选矩形遍历其内部格子,分别统计 0 和 1 的个数
| 方案 | 单次判定代价 | 可扩展性 |
|---|---|---|
| 0→−1 前缀和 | O(1) | 强(n, m 大也够) |
| 逐格统计 | O(nm) | 弱 |
第一行输入 n 和 m,随后 n 行 01 串。程序会找出黑白数量相等的最大子矩形。
点按钮开始 →
#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; }
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); | 面积 | 输出的是格子数,不是和 |
sum 当成答案输出(应该输出面积);③ 面积漏掉 +1,行数是 r2 - r1 + 1。写完程序后,用这些数据自查一遍:
| 输入 | 答案 | 考察点 |
|---|---|---|
4 5 | 16 | 题面样例 |
1 1 | 0 | 单格无法平衡,输出 0 |
1 2 | 2 | 一黑一白,恰好平衡 |
2 2 | 4 | 两黑两白,整个网格平衡 |
2 2 | 0 | 全是白格,不可能黑白相等 |
1 4 | 4 | 两黑两白,整行平衡 |
和 == 0就不代表黑白相等了,必须做映射。需要存网格和前缀和,各 10 × 10。
✅ 约 3000 次判定,任何语言瞬间完成。n, m ≤ 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) 矩形求和 | 子矩阵统计、图像分析 |
| 暴力枚举边界 | 四重循环 | 小规模网格的最优子矩形问题 |