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;
typedef long long ll;	// 严格要求
ll a[1010][1010]; 
int main(){
	ios :: sync_with_stdio(0);	// 提高cin、cout的运行速度
	ll n, m, maxn = 0;		//注意maxn最小也是0个 
	cin >> n >> m;
	
	for(ll i = 1; i <= n; i++){
		for(ll j = 1; j <= m; j++){
			cin >> a[i][j];
		}
	}
	
	for(ll i = 1; i <= n; i++){
		for(ll j = 1; j <= m; j++){
			
			//左上点（i，j）
			for(ll i1 = i; i1 <= n; i1++){
				for(ll j1 = j; j1 <= m; j1++){
					
					//右下点
					ll sum = 0;
					for(ll x = i; x <= i1; x++){
						for(ll y = j; y <= j1; y++){
							if(a[x][y] == 1){
								sum++;
							}
						}
					} 
					if(sum == (i1 - i + 1) * (j1 - j + 1)){		//全是1的情况 
						maxn = max(maxn, sum);
					}
				}
			} 
		}
	}
	
	cout << maxn << endl;

    return 0;
}