题目背景

对应的选择、判断题：试题 - GESP 202509 C++ 四级 - 洛谷有题

题目描述

作为将军，你自然需要合理地排兵布阵。地图可以视为 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 <iostream>
#include <vector>
using namespace std;

int main()
{
    int n,m;
    cin>>n>>m;
    vector<vector<int>> g(n,vector<int>(m));
    for(int i=0;i<n;i++)
        for(int j=0;j<m;j++)
            cin>>g[i][j];
    int maxarea=0;
    for(int x1=0;x1<n;x1++)
    {
        for(int x2=x1;x2<n;x2++)
        {
            for(int y1=0;y1<m;y1++)
            {
                for(int y2=y1;y2<m;y2++)
                {
                    bool ok=true;
                    for(int i=x1;i<=x2&&ok;i++)
                        for(int j=y1;j<=y2&&ok;j++)
                            if(g[i][j]==0) ok=false;
                    if(ok)
                    {
                        int area=(x2-x1+1)*(y2-y1+1);
                        if(area>maxarea) maxarea=area;
                    }
                }
            }
        }
    }
    cout<<maxarea;
    return 0;
}