一、先看原题
二、题目解析
1、《在方格王国里找最大草坪》
（1）想象这样一个世界 🏰：
这是一块方格王国
每个格子：
1= 🌱 草地（可以建房）0= 🌋 火山（不能建）
我们的任务是：
🏡 找一块全是草地的最大长方形区域，
给国王建一个大房子！
2、例如这样一张“地图” 🗺️
一个4 × 5 的地图：
行\列 1 2 3 4 5 1 1 1 0 1 1 2 1 1 0 1 1 3 1 1 1 1 1 4 0 1 1 1 03、最笨但最安全的办法是什么？🤔
🤷♂️不知道哪里最大，那就全部试一遍！
这就是我们首先想的方法：
👉枚举所有可能的矩形
4、如何“枚举所有矩形”？🧠
（1）一个矩形，需要4 个信息：
左上角：(x1, y1) 右下角：(x2, y2)（2）如果两个矩形的左上角相同，右下角也相同，这就是相同的矩形。
换句话说，如果两个矩形，只要左上角与右上角有一个不相同，就是不同的矩形
（3）所以我们枚举所有矩形：
1️⃣ 选左上角
2️⃣ 选右下角
3️⃣ 根据左上角，与右上角，枚举这个矩形内部的所有点，看看有不是全部都是1
4️⃣ 如果全部都是1，就与前面枚举的矩形面积比大小，更新max
👉 这就是使用最朴素枚举方法来解决这个问题！
5、参考程序：
#include <iostream> using namespace std; int a[25][25]; int n, m; int main() { cin >> n >> m; // 读入矩阵 for (int i = 1; i <= n; i++) { for (int j = 1; j <= m; j++) { cin >> a[i][j]; } } int ans = 0; // ① 枚举左上角行 for (int x1 = 1; x1 <= n; x1++) { // ② 枚举左上角列 for (int y1 = 1; y1 <= m; y1++) { // ③ 枚举右下角行 for (int x2 = x1; x2 <= n; x2++) { // ④ 枚举右下角列 for (int y2 = y1; y2 <= m; y2++) { bool ok = true; // ⑤ 枚举矩形内部行 for (int i = x1; i <= x2; i++) { // ⑥ 枚举矩形内部列 for (int j = y1; j <= y2; j++) { if (a[i][j] == 0) { ok = false; } } } // 如果这个矩形全是 1 if (ok) { int area = (x2 - x1 + 1) * (y2 - y1 + 1); ans = max(ans, area); } } } } } cout << ans << endl; return 0; }6、时间复杂度符合吗？
（1）先说结论
✅ 本题数据范围，n,m < 12，是可以通过的
（2）矩阵大小是：
n × m那么
| 循环 | 次数 |
|---|---|
| 左上角 | n × m |
| 右下角 | n × m |
| 检查内部 | n × m |
（3）👉 总复杂度大约是：
O(n² · m² · n · m) = O(n³ · m³)三、高阶提升：
🧠如何对朴素枚举程序进行优化呢？
（一）、使用二维前缀预处理，可以减少矩形合法性计算时间！
二维前缀和不能减少“枚举矩形的次数”，
但可以把“检查一个矩形是否合法”的复杂度
从 O(面积) 降到 O(1)
1、算法思路
原始朴素暴力（问题在哪）
每次：再扫一遍矩形内部，看是不是全 1
👉慢在“反复扫描矩形内部”
2、用二维前缀和之后
1️⃣预处理一个前缀和数组sum
2️⃣ 枚举所有矩形
3️⃣O(1) 判断矩形里 1 的个数
3、参考程序：
#include <iostream> using namespace std; int a[20][20]; int sum[20][20]; int main() { int n, m; cin >> n >> m; // 读入矩阵 for (int i = 1; i <= n; i++) { for (int j = 1; j <= m; j++) { cin >> a[i][j]; } } // 1️⃣ 计算二维前缀和 for (int i = 1; i <= n; i++) { for (int j = 1; j <= m; j++) { sum[i][j] = sum[i-1][j] + sum[i][j-1] - sum[i-1][j-1] + a[i][j]; } } int ans = 0; // 2️⃣ 枚举所有矩形 for (int x1 = 1; x1 <= n; x1++) { for (int x2 = x1; x2 <= n; x2++) { for (int y1 = 1; y1 <= m; y1++) { for (int y2 = y1; y2 <= m; y2++) { // 用前缀和 O(1) 计算矩形内 1 的个数 int ones = sum[x2][y2] - sum[x1-1][y2] - sum[x2][y1-1] + sum[x1-1][y1-1]; int area = (x2 - x1 + 1) * (y2 - y1 + 1); // 如果全是 1，更新答案 if (ones == area) { ans = max(ans, area); } } } } } cout << ans << endl; return 0; }4、时间复杂度
| 部分 | 复杂度 |
|---|---|
| 前缀和预处理 | O(nm) |
| 枚举矩形 | O(n²m²) |
| 矩形合法性判断 | O(1) |
👉总复杂度：O(n²m²)
（二）、固定上下边 + 压成一维（状态压缩）
1、算法一句话总览🎯
固定矩形的“上边”和“下边”，
把二维矩阵压缩成一维数组，
再在一维数组中找“最长连续 1 段”。
2、为什么这样能减少循环？
（1）原来（4 重循环）在枚举什么？
上边 + 下边 + 左边 + 右边👉 你是在枚举“矩形本身”
（2）现在（固定上下边）枚举什么？
上边 + 下边 + 一次横向扫描👉 是在枚举“高度”，横向找宽度
（3）本质变化
❌ 枚举矩形
✅ 枚举“高度 + 连续宽度”
3、核心思想拆解
1️⃣ 固定上下边
for (int top = 1; top <= n; top++) { for (int bottom = top; bottom <= n; bottom++) { ... } }👉 确定了矩形的高度
height = bottom - top + 1;2️⃣ 对每一列，判断“这一整列能不能用”
对某一列j：
如果
top ~ bottom这一列全是 1
👉 这一列是1只要有一个
0
👉 这一列是0
这样就得到一个一维 0/1 数组
3️⃣ 一维问题变成什么？
在 0/1 数组中，找最长连续的 1
我们已经非常熟悉了：
if (col[j] == 1) cnt++; else cnt = 0;4️⃣ 面积怎么计算？
面积 = 连续列数 * 高度4、【固定上下边 + 压成一维】完整参考程序
#include <iostream> using namespace std; int a[20][20]; int main() { int n, m; cin >> n >> m; // 读入矩阵 for (int i = 1; i <= n; i++) { for (int j = 1; j <= m; j++) { cin >> a[i][j]; } } int ans = 0; // 1️⃣ 固定上边 for (int top = 1; top <= n; top++) { // col[j] 表示：当前 top 到 bottom 之间， // 第 j 列是否全是 1 int col[20] = {0}; // 2️⃣ 枚举下边 for (int bottom = top; bottom <= n; bottom++) { // 更新每一列是否仍然“可用” for (int j = 1; j <= m; j++) { if (bottom == top) { // 第一行，直接赋值 col[j] = a[bottom][j]; } else { // 只要出现 0，这一列就废了 col[j] = col[j] && a[bottom][j]; } } // 当前矩形高度 int height = bottom - top + 1; // 3️⃣ 在 col[] 中找最长连续 1 int cnt = 0; for (int j = 1; j <= m; j++) { if (col[j] == 1) { cnt++; ans = max(ans, cnt * height); } else { cnt = 0; } } } } cout << ans << endl; return 0; }5、时间复杂度分析
| 部分 | 复杂度 |
|---|---|
| 枚举 top, bottom | O(n²) |
| 每次扫描列 | O(m) |
👉总复杂度：O(n² · m)
👉 比前缀和的O(n² · m²)明显更快
)
