A23725. 排兵布阵
填空题
较难
知识点
题目描述
排兵布阵
题目描述
作为将军，你自然需要合理地排兵布阵。地图可以视为n 行 m列的网格，适合排兵的网格以 1 标注，不适合排兵的网格以 0 标注。现在你需要在地图上选择一个矩形区域排兵，这个矩形区域内不能包含不适合排兵的网格。请问可选择的矩形区域最多能包含多少网格？
输入格式
第一行，两个正整数n,m ，分别表示地图网格的行数与列数。
接下来n 行，每行m 个整数ai,1,ai,2,...,ai,m ，表示各行中的网格是否适合排兵。
输出格式
一行，一个整数，表示适合排兵的矩形区域包含的最大网格数。
样例
输入样例 1
4 3
0 1 1
1 0 1
0 1 1
1 1 1输出样例 1
4输入样例 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 <algorithm>
#include <cstdio>
using namespace std;
const int N = 15;
int n, m;
int a[N][N];
int ans;
int main() {
scanf("%d%d", &n, &m);
for (int i = 1; i <= n; i++)
for (int j = 1; j <= m; j++) scanf("%d", &a[i][j]);
for (int u = 1; u <= n; u++)
for (int l = 1; l <= m; l++)
for (int d = u; d <= n; d++) {
int chk = 1;
for (int r = l; r <= m; r++) {
for (int x = u; x <= d; x++) chk &= a[x][r];
if (!chk) break;
ans = max(ans, (r - l + 1) * (d - u + 1));
}
}
printf("%d\n", ans);
return 0;
}
上一题
下一题