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;
}

{
    cin >> n >> m;
     ( i = ; i <= n; i++) {
         ( j = ; j <= m; j++) {
            cin >> a[i][j];
        }
    }
     ( i = ; i <= n; i++) {
        
         ( j = ; j <= m; j++) {
            
             ( k = i; k <= n; k++) {
                
                 ( l = j; l <= m; l++) {
                    
                     ((i, j, k, l)) {
                        
                        ans = (ans, (k - i + ) * (l - j + ));
                        
                    }
                }
            }
        }
    }
    cout << ans;
     ;
}