2024年华为OD机试真题-分配土地-(C++/Java/python)-OD统一考试（C卷D卷）_从前有个村庄,村民们喜欢在各种田地上插上小旗子,旗子上标识了各种不同的数字。某

题目描述

从前有个村庄，村民们喜欢在各种田地上插上小旗子，旗子上标识了各种不同的数字。

某天集体村民决定将覆盖相同数字的最小矩阵形的土地分配给村里做出巨大贡献的村民，

请问此次分配土地，做出贡献的村民种最大会分配多大面积?

输入描述

第一行输入 m 和 n，

m 代表村子的土地的长

n 代表土地的宽

第二行开始输入地图上的具体标识

输出描述

此次分配土地，做出贡献的村民种最大会分配多大面积

备注

旗子上的数字为1~500，土地边长不超过500

未插旗子的土地用0标识

用例1

输入

3 3

1 0 1

0 0 0

0 1 0

输出

9

说明

土地上的旗子为1，其坐标分别为(0,0)，(2,1)以及(0,2)，为了覆盖所有旗子，

矩阵需要覆盖的横坐标为0和2，纵坐标为0和2，所以面积为9，即（2-0+1）*（2-0+1）= 9

用例2

输入

3 3

1 0 2

0 0 0

0 3 4

输出

1

说明

由于不存在成对的小旗子,所以最小矩形面积是一块地的面积，为1.

考点

数据结构，逻辑分析

解题思路

1.统计出相同数字所在的坐标，对相同数字的坐标求横纵坐标的最大最小值。

2.比较出每个数字覆盖面积中的最大面积。

代码 

c++

#include <bits/stdc++.h>
using namespace std;
 
int main() {
    int m,n;
    cin>>m>>n;
    vector<vector<int>> mat(m, vector<int>(n));
    map<int,vector<pair<int,int>>> mp;
    for(int i=0;i<m;i++) {
        for(int j=0;j<n;j++) {
            cin>>mat[i][j];
            if(mat[i][j]>0) {
                mp[mat[i][j]].push_back((pair<int,int>){i,j});
            }
        }
    }
    int res=0;
    for(auto a:mp) {
        int xh=0,xl=500, yh=0,yl=500;
        for(auto p:a.second) { //p是坐标
            xh=max(xh,p.first);
            xl=min(xl,p.first);
            yh=max(yh,p.second);
            yl=min(yl,p.second);
        }
        int sq=(yh-yl+1)*(xh-xl+1);
        res=max(res,sq);
    }
    cout<<res<<