在 0/1 网格中找全为 1 的最大矩形区域,输出其包含的网格数。
地图是 n 行 m 列的网格,适合排兵的格子标 1、不适合的标 0。现在需要选一个矩形区域排兵,要求区域内不能包含任何 0。问可选的矩形区域最多能包含多少个网格。
最大全 1 矩形枚举边界数据量小前缀和验证
| 项目 | 说明 |
|---|---|
| 输入 | 第一行 n、m;随后 n 行每行 m 个 0/1 |
| 输出 | 全 1 矩形的最大网格数(面积) |
| 数据范围 | 1 ≤ n, m ≤ 12 |
| 网格值 | 0 或 1 |
| 合法区域 | 矩形内部不能含有 0 |
0 1 1 1 0 1 0 1 1 1 1 1
第 1 行:0 1 1 → 含 0,不行
第 2 行:1 0 1 → 含 0,不行
第 3 行:0 1 1 → 含 0,不行
第 4 行:1 1 1 → 全是 1,面积 3
目前最好:3
第 3~4 行、第 2~3 列:
第 3 行第 2~3 列 = 1 1
第 4 行第 2~3 列 = 1 1
四格全是 1 → 面积 4
✅ 刷新为 4
2 × 3 需要两行全是 1,但只有第 4 行满足
3 × 2 需要某两列连续三行全 1,检查后不成立
3 × 3 显然不行(第 1 行有 0)
✅ 最大值是 4
| 候选矩形 | 位置 | 面积 | 是否全 1 |
|---|---|---|---|
| 1 × 3 | 第 4 行 | 3 | ✅ |
| 2 × 2 | 第 3~4 行、第 2~3 列 | 4 | ✅ |
| 2 × 3 | 第 2~3 行 | — | ❌ 含 0 |
| 3 × 3 | 任意位置 | — | ❌ 含 0 |
答案 4 ✓
1 0 1 0 1 0 1 0 1 0 0 1 1 1 0
| 候选矩形 | 位置 | 面积 | 是否全 1 |
|---|---|---|---|
| 1 × 3 | 第 3 行第 2~4 列(1 1 1) | 3 | ✅ |
| 2 × 1 | 第 2~3 行某列 | 2 | ✅ |
| 2 × 2 | 任意位置 | — | ❌ 均含 0 |
| 1 × 5 | 任意行 | — | ❌ 均含 0 |
答案 3 ✓
枚举上下左右边界,逐格检查是否全 1
把问题逐行转化成"柱状图中的最大矩形"
| 方案 | 本题运算量 | n=m=1000 时 |
|---|---|---|
| 四重循环 | 约 10⁶ | 约 10¹²(超时) |
| 单调栈 | 约 1.4 × 10² | 约 10⁶(可行) |
第一行输入 n 和 m,随后 n 行每行 m 个 0/1,程序会找出最大的全 1 矩形并高亮它。
点按钮开始 →
#include <bits/stdc++.h> using namespace std; int a[15][15]; int main() { int n, m; scanf("%d %d", &n, &m); for (int i = 0; i < n; i++) for (int j = 0; j < m; j++) scanf("%d", &a[i][j]); int ans = 0; // 四重循环枚举矩形的上下左右边界 for (int r1 = 0; r1 < n; r1++) { for (int r2 = r1; r2 < n; r2++) { for (int c1 = 0; c1 < m; c1++) { for (int c2 = c1; c2 < m; c2++) { int ones = 0; int area = (r2 - r1 + 1) * (c2 - c1 + 1); // 统计矩形内 1 的个数 for (int i = r1; i <= r2; i++) for (int j = c1; j <= c2; j++) if (a[i][j] == 1) ones++; // 1 的个数等于面积,说明全是 1 if (ones == area && area > ans) ans = area; } } } } printf("%d\n", ans); return 0; }
| 代码 | 作用 | 为什么这样写 |
|---|---|---|
r2 = r1 作为内层起点 | 保证 r2 ≥ r1 | 下边界不能在上边界之上 |
(r2-r1+1) * (c2-c1+1) | 计算面积 | 行数 × 列数,注意 +1 |
if (ones == area) | 判定全 1 | 1 的个数等于格数,说明没有 0 |
if (area > ans) ans = area; | 取最大 | 只有全 1 的矩形才参与比较 |
r2 = r1 + 1 起步,会漏掉所有"只有一行"的矩形;② 面积算成 (r2-r1)*(c2-c1),漏掉 +1;③ 只统计了 1 的个数却没和面积比较,导致含 0 的矩形也被算进去。写完程序后,用这些数据自查一遍:
| 输入 | 答案 | 考察点 |
|---|---|---|
4 3 | 4 | 题面样例 1 |
3 5 | 3 | 题面样例 2 |
1 1 | 1 | 单格且为 1 |
2 2 | 4 | 全 1,整块都是 |
2 2 | 1 | 只能选单个格子 |
1 4 | 4 | 单行横向全 1 |
只需一个 12 × 12 的网格数组。
✅ 约 100 万次运算,任何语言都能瞬间完成。数据范围小是这个解法成立的前提。
// 用"计数 == 面积"判断全 1(配合二维前缀和可做到 O(1)) long long pre[15][15]; // 矩形内 1 的个数 = 矩形和(因为 0 不贡献) long long ones = pre[r2+1][c2+1] - pre[r1][c2+1] - pre[r2+1][c1] + pre[r1][c1]; long long area = (r2-r1+1) * (c2-c1+1); if (ones == area) { /* 全 1 */ } // 当 n, m 很大时的进阶做法:逐行转化为柱状图最大矩形(单调栈) // 对每一行 i,维护 h[j] = 以 (i,j) 结尾的连续 1 的个数 // 然后在 h[] 上用单调栈求最大矩形面积,整体 O(nm) for (int j = 0; j < m; j++) h[j] = a[i][j] ? h[j] + 1 : 0; // ... 单调栈求 h[] 中的最大矩形 // 经典结论:n × m 网格中矩形总数 = n(n+1)/2 × m(m+1)/2
把这道题用到的基本功拆出来,它们能迁移到很多同类问题上。
| 能力点 | 本题怎么用 | 还能迁移到 |
|---|---|---|
| 枚举边界 | 四重循环给出所有矩形 | 小规模网格的暴力解法 |
| 计数 == 面积 | 判断区域是否全是 1 | 棋盘、图像、区域判定 |
| 按数据范围选算法 | 12 用暴力、1000 用单调栈 | 所有题目的第一步决策 |
ones == area 换成 ones * 2 >= area,统计方式不变。这说明"计数 == 面积"只是判定的一个特例,换成任意关于计数的条件都很容易扩展。)