B4415 [GESP202509 四级] 排兵布阵

题目描述

作为将军，你自然需要合理地排兵布阵。地图可以视为 $n$ 行 $m$ 列的网格，适合排兵的网格以 1 标注，不适合排兵的网格以 0 标注。现在你需要在地图上选择一个矩形区域排兵，这个矩形区域内不能包含不适合排兵的网格。请问可选择的矩形区域最多能包含多少网格？

输入格式

第一行，两个正整数 $n,m$，分别表示地图网格的行数与列数。

接下来 $n$ 行，每行 $m$ 个整数 $a_{i,1},a_{i,2},\dots ,a_{i,m}$，表示各行中的网格是否适合排兵。

输出格式

一行，一个整数，表示适合排兵的矩形区域包含的最大网格数。

输入输出样例 #1

输入 #1

4 3
0 1 1
1 0 1
0 1 1
1 1 1

输出 #1

4

输入输出样例 #2

输入 #2

3 5
1 0 1 0 1
0 1 0 1 0
0 1 1 1 0

输出 #2

3

说明/提示

对于所有测试点，保证 $1\le n,m\le 12$，$0\le a_{i,j}\le 1$。

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

int main() {
    int n, m;
    cin >> n >> m;

    int a[110][110];
    for (int i = 0; i < n; i++)
        for (int j = 0; j < m; j++)
            cin >> a[i][j];

    int maxArea = 0;

    // 从每个格子出发
    for (int i1 = 0; i1 < n; i1++) {
        for (int j1 = 0; j1 < m; j1++) {

            // 只有是1的格子才可以作为左上角
            if (a[i1][j1] == 0) continue;

            // 向右下扩张
            for (int i2 = i1; i2 < n; i2++) {
                for (int j2 = j1; j2 < m; j2++) {
                    
                    bool allOne = true;
                    // 检查这个矩形是否全是1
                    for (int x = i1; x <= i2; x++) {
                        for (int y = j1; y <= j2; y++) {
                            if (a[x][y] == 0) {
                                allOne = false;
                                break;
                            }
                        }
                        if (!allOne) break;
                    }

                    if (allOne) {
                        int area = (i2 - i1 + 1) * (j2 - j1 + 1);
                        if (area > maxArea)
                            maxArea = area;
                    }
                }
            }
        }
    }

    cout << maxArea << endl;
    return 0;
}

🧩 题目回顾

地图上：

• 1 表示可以排兵；
• 0 表示不可以。

要找：由全是 1 的小方格组成的最大矩形，看看它最多能有多少格。

🌱 思路讲解

想象你有一张地图，用 0 和 1 画的。

比如：

1 1 0
1 1 1
1 1 1

我们可以从每一个“1”出发，往右下角扩张，看看能形成多大的矩形。

每次只要矩形里有“0”，就不能再扩张了。

把所有可能矩形都试一遍，记录面积最大的那个。

🎯 例子演示

输入：

3 3
1 1 0
1 1 1
1 1 1

输出：

6

解释：
最大的矩形是：

1 1
1 1
1 1

面积是 3×2=6。

💬 总结一句话

“从每个 1 出发，往右下角找最大的全 1 矩形，面积最大值就是答案。”