CCF-GESP计算机学会等级考试2025年9月四级C++T1 排兵布阵
B4415 [GESP202509 四级] 排兵布阵
题目描述
作为将军，你自然需要合理地排兵布阵。地图可以视为 nnn 行 mmm 列的网格，适合排兵的网格以 1 标注，不适合排兵的网格以 0 标注。现在你需要在地图上选择一个矩形区域排兵，这个矩形区域内不能包含不适合排兵的网格。请问可选择的矩形区域最多能包含多少网格？
输入格式
第一行，两个正整数 n,mn, mn,m，分别表示地图网格的行数与列数。
接下来 nnn 行，每行 mmm 个整数 ai,1,ai,2,…,ai,ma_{i,1}, a_{i,2}, \ldots, a_{i,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≤121 \leq n, m \leq 121≤n,m≤12，0≤ai,j≤10 \leq a_{i,j} \leq 10≤ai,j≤1。
解析
暴力枚举法，详见代码：
#include<bits/stdc++.h>usingnamespace std;int m,n;int a[105][105];int ans=0;//计算bx（开始行），by（开始列），ex（结束行），ey（结束列）//范围是否都可以排兵 boolf(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){return0;}}}return1;}intmain(){ cin>>m>>n;for(int i=1;i<=m;i++){for(int j=1;j<=n;j++){ cin>>a[i][j];}}for(int i=1;i<=m;i++){//枚举矩形左上角行for(int j=1;j<=n;j++){//枚举矩形左上角列for(int k=i;k<=m;k++){//枚举矩形右下角行for(int l=j;l<=n;l++){//枚举矩形右下角列if(f(i,j,k,l)){//若符合条件 ans=max(ans,(k-i+1)*(l-j+1));//求面积的最大值 }}}}} cout<<ans;return0;}
