GESP 题解库 / 4 级题解 / [GESP202509 四级] 排兵布阵 · 第 6 / 25 题
GESP202509 四级 · B4415 · 简单

排兵布阵

在 0/1 网格中找全为 1 的最大矩形区域,输出其包含的网格数。

📊
n, m ≤ 12
网格规模
🔢
int
数值类型
⚡
O(n²m²)
时间复杂度
🎯
枚举矩形边界
核心算法
01
题目拆解
把题目拆成一块块,看清全貌

📝 题目原文

地图是 n 行 m 列的网格,适合排兵的格子标 1、不适合的标 0。现在需要选一个矩形区域排兵,要求区域内不能包含任何 0。问可选的矩形区域最多能包含多少个网格。

💡
人话翻译:找出一个"全是 1 的矩形",让它包含的格子最多。注意 n, m ≤ 12,数据非常小——这暗示我们可以用比较暴力的做法:直接枚举矩形的上下左右四条边。

🔍 关键词提取

最大全 1 矩形枚举边界数据量小前缀和验证

已知条件

项目说明
输入第一行 n、m;随后 n 行每行 m 个 0/1
输出全 1 矩形的最大网格数(面积)
数据范围1 ≤ n, m ≤ 12
网格值0 或 1
合法区域矩形内部不能含有 0

需要解决的问题

02
思维导图
整理解题思路的全貌
🎯 四重循环枚举矩形
📥 读入
n、m ≤ 12
0/1 网格
数据极小是重要提示
int 足够
🎯 枚举边界
r1 上边界
r2 下边界(r2 ≥ r1)
c1 左边界
c2 右边界(c2 ≥ c1)
✅ 验证全 1
统计区域内 1 的个数
个数 == 面积 → 全 1
或用二维前缀和 O(1)
合格就更新最大面积
⚠️ 易错点
边界循环范围写错
忘记 r2 ≥ r1
只数 1 的个数却搞错面积
max 初始化
03
样例手算推导
样例两组逐个寻找

🧮 样例 1:4 × 3 网格,答案 4

0 1 1
1 0 1
0 1 1
1 1 1
1
先看能否找到 1 × 3 的横条

第 1 行:0 1 1 → 含 0,不行

第 2 行:1 0 1 → 含 0,不行

第 3 行:0 1 1 → 含 0,不行

第 4 行:1 1 1 → 全是 1,面积 3

目前最好:3

2
再看 2 × 2 的方块

第 3~4 行、第 2~3 列:

第 3 行第 2~3 列 = 1 1

第 4 行第 2~3 列 = 1 1

四格全是 1 → 面积 4

✅ 刷新为 4

3
能更大吗?

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 ✓

🧮 样例 2:3 × 5 网格,答案 3

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 ✓

🔑
这道题的数据范围是"善意提示":n, m ≤ 12 意味着最多 12 × 12 = 144 个格子,矩形总数约 6000 个,每个最多检查 144 格 → 总共不到 100 万次运算。看到这么小的数据范围,就该放心用暴力枚举。如果 n, m 是 10³ 甚至 10⁵,那才需要用单调栈之类的进阶方法。
04
解法对比
四重循环暴力 vs 悬垂线/单调栈

⚔️ 解法对比

🟢 四重循环暴力(推荐) 推荐

枚举上下左右边界,逐格检查是否全 1

  • 时间 O(n²m² × nm)
  • 本题约 10⁶ 次,极快
  • 代码 15 行
  • 几乎不会写错
💡
为什么推荐暴力:n, m ≤ 12 时暴力上限约 100 万次运算,远低于时间限制。用简单方法解决小数据,是最稳妥的策略。

🟠 单调栈求最大矩形

把问题逐行转化成"柱状图中的最大矩形"

  • 时间 O(n × m),更快
  • 但代码复杂(约 40 行)
  • 需要理解单调栈
  • 对本题属于过度设计
⚠️
什么时候必须用:当 n, m 达到 10³ 时,暴力 O(n²m² × nm) 会超时,那时单调栈(O(nm))就是必修课了。建议:先掌握暴力,再学单调栈。

📈 性能对比

方案本题运算量n=m=1000 时
四重循环约 10⁶约 10¹²(超时)
单调栈约 1.4 × 10²约 10⁶(可行)
05
算法流程图
枚举边界 + 验证全 1
开始读入 n、m 和网格;ans = 0枚举上边界 r1、下边界 r2(r2 ≥ r1)枚举左边界 c1、右边界 c2(c2 ≥ c1)统计矩形内 1 的个数,面积 = (r2−r1+1) × (c2−c1+1)1 的个数 == 面积吗?是 ✓ans = max(ans, 面积)否 ✗含 0,跳过输出 ans结束还有边界组合 → 继续枚举
← 左右滑动查看完整流程图
06
动手算一算
自己输入数据试试看

🎯 最大全 1 矩形查找器

第一行输入 n 和 m,随后 n 行每行 m 个 0/1,程序会找出最大的全 1 矩形并高亮它。

结果会显示在这里

点按钮开始 →

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

💻 完整 C++ 代码

#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;
}
🔑
"全是 1"的判定技巧:先算出矩形面积,再数里面有几个 1。如果个数 == 面积,就说明每格都是 1。这个"用计数代替逐格判断"的思路很常用,配合二维前缀和还能把判断降到 O(1)。

📖 关键几行怎么看

代码作用为什么这样写
r2 = r1 作为内层起点保证 r2 ≥ r1下边界不能在上边界之上
(r2-r1+1) * (c2-c1+1)计算面积行数 × 列数,注意 +1
if (ones == area)判定全 11 的个数等于格数,说明没有 0
if (area > ans) ans = area;取最大只有全 1 的矩形才参与比较
⚠️
三个坑:① 边界循环写成 r2 = r1 + 1 起步,会漏掉所有"只有一行"的矩形;② 面积算成 (r2-r1)*(c2-c1),漏掉 +1;③ 只统计了 1 的个数却没和面积比较,导致含 0 的矩形也被算进去。
08
边界测试 & 易错点
把坑都踩一遍,考试不翻车

🧪 边界测试用例表

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

输入答案考察点
4 3
0 1 1 / 1 0 1 / 0 1 1 / 1 1 1
4题面样例 1
3 5
1 0 1 0 1 / 0 1 0 1 0 / 0 1 1 1 0
3题面样例 2
1 1
1
1单格且为 1
2 2
1 1 / 1 1
4全 1,整块都是
2 2
1 0 / 0 1
1只能选单个格子
1 4
1 1 1 1
4单行横向全 1
✅
自查清单:① 四个边界循环范围对吗?② 面积公式对了吗?③ 验证过"全 1"吗?

🚨 易错点清单

⚠️
下边界从上边界开始:必须允许 r2 = r1,否则会漏掉所有单行矩形。
⚠️
面积公式漏 +1:行数是 r2 − r1 + 1,列数是 c2 − c1 + 1。
⚠️
没有验证"全 1":必须比较 1 的个数与面积,否则含 0 的矩形也会被统计。
09
复杂度分析
算算效率怎么样

📊 复杂度四宫格

时间复杂度
O(n²m² × nm)
空间复杂度
O(nm)
n, m 最大
12
最坏运算
约 10⁶

时间怎么算的?

空间都用在哪?

只需一个 12 × 12 的网格数组。

✅ 约 100 万次运算,任何语言都能瞬间完成。数据范围小是这个解法成立的前提。

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

🔗 常用技巧小抄

// 用"计数 == 面积"判断全 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 用单调栈所有题目的第一步决策
🌟
思考题:如果题目要求矩形内1 的个数不少于 0 的个数(而不是全为 1),暴力解法要改哪里?(提示:把 ones == area 换成 ones * 2 >= area,统计方式不变。这说明"计数 == 面积"只是判定的一个特例,换成任意关于计数的条件都很容易扩展。)