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