最新华为OD机试真题-土地分配(100分)

大家好这里是清隆学长 ，一枚热爱算法的程序员

✨ 本系列打算持续跟新华为OD-C/D卷的三语言AC题解

ACM银牌| 多次AK大厂笔试 ｜ 编程一对一辅导

感谢大家的订阅➕ 和 喜欢

在线评测链接

=> 土地分配(100分) <=

评测功能需要 =>订阅专栏<= 后联系清隆解锁～

OJ题目截图

土地分配

题目描述

LYA所在的村庄有一片 的矩形田地，村民们喜欢在田地上插上写有数字的旗子。现在村民们决定，将覆盖相同数字旗子的最小矩形土地分配给对应的村民。请问此次土地分配中，面积最大的一块土地有多大？

输入格式

第一行输入两个整数 和 ，分别表示田地的长和宽，两个整数之间用空格隔开。

接下来的 行，每行包含 个整数，表示该位置上旗子的数字。相邻两个整数之间用空格隔开，其中 表示该位置没有插旗子。

输出格式

输出一个整数，表示分配给村民的土地中，面积最大的一块的面积。

样例输入1

3 3
1 0 2
0 0 0
3 0 4

样例输出1

1

说明：田地上没有相同数字的旗子，所以每块分配的土地面积都为 。

样例输入2

3 3
1 0 1
0 0 0
0 1 0

样例输出2

9

说明：田地上有 个旗子的数字为 ，它们的坐标分别为 、 和 ，覆盖这些旗子的最小矩形土地面积为 。

数据范围

旗子上的数字

题解

我们可以用一个哈希表来存储每个数字对应的旗子的坐标范围，即左上角和右下角的行列号。遍历整个田地，对于每个非零的数字，更新其在哈希表中对应的坐标范围。最后，遍历哈希表中的每个数字，计算其对应的矩形土地面积，取最大值即可。

具体实现时，可以用一个二维数组来存储田地上的数字，用一个哈希表来存储每个数字对应的坐标范围，其中键为数字，值为一个长度为 的数组，分别表示左上角的行号、右下角的行号、左上角的列号和右下角的列号。

时间复杂度为 ，空间复杂度为 。

参考代码

• Python

m, n = map(int, input().split())
field = [list(map(int, input().split())) for _ in range(m)]

coords = {}
for i in range(m):
    for j in range(n):
        if field[i][j] != 0:
            num = field[i][j]
            if num not in coords:
                coords[num] = [i, i, j, j]
            else:
                coords[num][0] = min(coords[num][0], i)
                coords[num][1] = max(coords[num][1], i)
                coords[num][2] = min(coords[num][2], j)
                coords[num][3] = max(coords[num][3], j)

max_area = 0
for r1, r2, c1, c2 in coords.values():
    max_area = max(max_area, (r2 - r1 + 1) * (c2 - c1 + 1))

print(max_area)

• Java

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

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int m = sc.nextInt();
        int n = sc.nextInt();
        int[][] field = new int[m][n];
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                field[i][j] = sc.nextInt();
            }
        }
        
        Map<Integer, int[]> coords = new HashMap<>();
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (field[i][j] != 0) {
                    int num = field[i][j];
                    if (!coords.containsKey(num)) {
                        coords.put(num, new int[]{i, i, j, j});
                    } else {
                        int[] range = coords.get(num);
                        range[0] = Math.min(range[0], i);
                        range[1] = Math.max(range[1], i);
                        range[2] = Math.min(range[2], j);
                        range[3] = Math.max(range[3], j);
                    }
                }
            }
        }
        
        int maxArea = 0;
        for (int[] range : coords.values()) {
            maxArea = Math.max(maxArea, (range[1] - range[0] + 1) * (range[3] - range[2] + 1));
        }
        
        System.out.println(maxArea);
    }
}

• Cpp

#include <iostream>
#include <vector>
#include <unordered_map>
using namespace std;

int main() {
    int m, n;
    cin >> m >> n;
    vector<vector<int>> field(m, vector<int>(n));
    for (int i = 0; i < m; i++) {
        for (int j = 0; j < n; j++) {
            cin >> field[i][j];
        }
    }
    
    unordered_map<int, vector<int>> coords;
    for (int i = 0; i < m; i++) {
        for (int j = 0; j < n; j++) {
            if (field[i][j] != 0) {
                int num = field[i][j];
                if (coords.count(num) == 0) {
                    coords[num] = {i, i, j, j};
                } else {
                    coords[num][0] = min(coords[num][0], i);
                    coords[num][1] = max(coords[num][1], i);
                    coords[num][2] = min(coords[num][2], j);
                    coords[num][3] = max(coords[num][3], j);
                }
            }
        }
    }
    
    int maxArea = 0;
    for (auto& p : coords) {
        int r1 = p.second[0], r2 = p.second[1], c1 = p.second[2], c2 = p.second[3];
        maxArea = max(maxArea, (r2 - r1 + 1) * (c2 - c1 + 1));
    }
    
    cout << maxArea << endl;
    
    return 0;
}