CCF-GESP 2025 年 9 月四级 C++ 真题解析：排兵布阵

题目描述

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

输入格式

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

接下来 n 行，每行 m 个整数 ai,1,ai,2,…,ai,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≤n,m≤12，0≤ai,j≤1。

解析

暴力枚举法，详见代码：

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

int m, n;
int a[105][105];
int ans = 0;

// 计算 bx（开始行），by（开始列），ex（结束行），ey（结束列）
// 范围是否都可以排兵
bool f(int bx, int by, int ex, int ey) {
    for (int i = bx; i <= ex; i++) {
        for (int j = by; j <= ey; j++) {
            if (a[i][j] == 0) {
                return 0;
            }
        }
    }
    return 1;
}

int main() {
    cin >> n >> m;
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            cin >> a[i][j];
        }
    }
    for (int i = 1; i <= n; i++) {
        // 枚举矩形左上角行
        for (int j = 1; j <= m; j++) {
            // 枚举矩形左上角列
            for (int k = i; k <= n; k++) {
                // 枚举矩形右下角行
                for (int l = j; l <= m; l++) {
                    // 枚举矩形右下角列
                    if (f(i, j, k, l)) {
                        // 若符合条件
                        ans = max(ans, (k - i + 1) * (l - j + 1));
                        // 求面积的最大值
                    }
                }
            }
        }
    }
    cout << ans;
    return 0;
}