题目描述

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

某天集体村民决定将覆盖相同数字的最小矩阵形的土地分配给村里做出巨大贡献的村民，请问此次分配土地，做出贡献的村民种最大会分配多大面积?

输入描述

第一行输入 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，即一块土地的面积。

Java

import java.util.HashMap;
import java.util.Map;
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        // 土地的长和宽
        int m = scanner.nextInt();
        int n = scanner.nextInt();

        // 二维数组存储土地上的标识
        int[][] land = new int[m][n];
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                land[i][j] = scanner.nextInt();
            }
        }

        // 哈希表存储每个数字的最小和最大位置
        Map<Integer, int[]> minPos = new HashMap<>();
        Map<Integer, int[]> maxPos = new HashMap<>();

        // 遍历每块土地，更新每个数字的最小和最大位置
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                int num = land[i][j];
                if (num != 0) {
                    if (!minPos.containsKey(num)) {
                        minPos.put(num, new int[]{i, j});
                        maxPos.put(num, new int[]{i, j});
                    } else {
                        minPos.get(num)[0] = Math.min(minPos.get(num)[0], i);
                        minPos.get(num)[1] = Math.min(minPos.get(num)[1], j);
                        maxPos.get(num)[0] = Math.max(maxPos.get(num)[0], i);
                        maxPos.get(num)[1] = Math.max(maxPos.get(num)[1], j);
                    }
                }
            }
        }

        // 初始化
        int maxArea = 0;

        // 遍历每个数字，计算其对应的面积，并更新最大面积
        for (Integer num : minPos.keySet()) {
            int[] min = minPos.get(num);
            int[] max = maxPos.get(num);
            int area = (max[0] - min[0] + 1) * (max[1] - min[1] + 1);
            maxArea = Math.max(maxArea, area);
        }

        // 打印最大面积
        System.out.println(maxArea);
        scanner.close();
    }
}

C++贪心

#include<bits/stdc++.h>
using namespace std;

struct ST{
	int x_l = -1;
	int x_r = 501;
	int y_h = 501;
	int y_l = -1;
	int cnt;
};

int main(){
	int m,n;
	cin>>m>>n;
	
	vector<vector<int>> mp(m,vector<int>(n));
	map<int,ST> dic;
	
	for(int i=0;i<m;i++){
		for(int j=0;j<n;j++){
			cin>>mp[i][j];
			if(mp[i][j] == 0) continue;
			dic[mp[i][j]].cnt++;
			if(i>dic[mp[i][j]].x_r || dic[mp[i][j]].x_r == 501) dic[mp[i][j]].x_r = i;
			if(i<dic[mp[i][j]].x_l || dic[mp[i][j]].x_l == -1) dic[mp[i][j]].x_l = i;
			if(j>dic[mp[i][j]].y_h || dic[mp[i][j]].y_h == 501) dic[mp[i][j]].y_h = j;
			if(j<dic[mp[i][j]].y_l || dic[mp[i][j]].y_l == -1) dic[mp[i][j]].y_l = j;
		}
	}

	int res = 0;
	
	for(auto x:dic){
		if(x.second.cnt == 1){
			res = max(res,1);
			continue;
		}
		int chang = (x.second.x_r - x.second.x_l+1);
		int kuan = (x.second.y_h - x.second.y_l+1);
		res = max(res,chang*kuan);
	}
	cout<<res<<endl;
}