题目描述与示例

题目描述

从前有个村庄，村民们喜欢在各种田地上插上小旗子，旗子上标识了各种不同的数字。某天集体村民决定将覆盖相同数字的最小矩阵形的土地的分配给为村里做出巨大贡献的村民，请问，此次分配土地，做出贡献的村民中最大会分配多大面积?

输入描述

第一行输入 m 和 n，m 代表村子的土地的长，n 代表土地的宽

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

输出描述

输出需要分配的土地面积，即包含相同数字旗子的最小矩阵中的最大面积。

备注

旗子上的数字为 1-500，土地边长不超过 500 未插旗子的土地用 0 标识

示例一

输入

3 3
1 0 1
2 0 2
0 1 0

输出

9

说明

土地上的旗子为 1，其坐标分别为(0,0)，(2,1)以及(0,2)，为了覆盖所有旗子，矩阵需要覆盖的横坐标为 0 和 2，纵坐标为 0 和 2，所以面积为 9，即(2-0+1)*(2-0+1)=9。

示例二

输入

3 3

输出

1

说明

由于不存在成对的小旗子，故而返回 1，即一块土地的面积。

解题思路

这道题乍一看可能没有思路。因为不同颜色的最小覆盖面积的计算是没有关联的，所以本题应该分为两个大步骤思考这个题目：

  1. 如何计算单种颜色的最小覆盖面积
  2. 求出所有颜色的最小覆盖面积中的最大值

单种颜色的最小覆盖面积

一个矩形的面积取决于四条边的位置。以示例一为例，如果要覆盖所有包含1的旗子，矩阵的上、下、左、右必须分别位于0，3，0，3的位置。故此时矩形的最小覆盖面积为(3-0)*(3-0) = 9

而矩形的四条边的位置则取决于同色旗子位于最上边的点、最下边的点、最左边的点、最右边的点。因此我们只需要记录同种颜色的点的四个最值即可很方便地求出覆盖某种颜色的矩形的最小面积。

对于同种颜色可以用一个长度为4的列表[top, bottom, left, right]来记录这四个最值信息。对于该颜色某一个点的坐标(x, y)

  • 考虑上下方向，若
    • 这个点比之前记录过的最上边的点更加偏上，即x < top，则更新top = x
    • 这个点比之前记录过的最下边的点更加偏下，即x > bottom，则更新bottom = x
  • 考虑左右方向，若
    • 这个点比之前记录过的最左边的点更加偏左，即y < left，则更新left = y
    • 这个点比之前记录过的最下边的点更加偏下，即y > right，则更新right = y

这样只需遍历一次grid数组，对所有同种颜色的点都进行上述过程，就可以求出该种颜色的最小覆盖面积了。

上述分析过程，本质上也是一种贪心思想的体现，因为四个最值所围成的矩形，就一定能够覆盖插有同色旗子的所有点了。

多种颜色的最小覆盖面积

由于颜色最多有500种，我们自然不希望循环考虑500次不同的颜色，每一次都遍历grid数组。

我们希望只需一次遍历grid数组，就能够将所有颜色的最值信息都得到。考虑如何储存不同颜色的长度为4的最值信息列表，那么答案很显而易见——使用哈希表。

其中哈希表的key为不同的颜色，value为上一小节所述的长度为4的最值信息列表。

代码

Python

# 题目：【贪心】2023C-分配土地最大面积
# 分值：100
# 作者：闭着眼睛学数理化
# 算法：贪心
# 代码看不懂的地方，请直接在群上提问


from collections import defaultdict
from math import inf


# 输入二维矩阵的长、宽
m, n = map(int, input().split())
grid = list()
# 循环m行，每次输入长度为n的一维数组
for _ in range(m):
    grid.append(list(map(int, input().split())))


# 构建哈希表dic，其中
# key为表示某种颜色的数字
# value为该种颜色对应的长度为4最值列表[top, bottom, left, right]
# 初始化top和left为正无穷（或者500，因为边长最大为500），
# 初始化，bottom和right为负无穷（或者-1）
dic = defaultdict(lambda : [inf, -inf, inf, -inf])

# 遍历整个二维矩阵grid
for x in range(m):
    for y in range(n):
        # 获得该种颜色
        color = grid[x][y]
        # 如果没有插旗子，则直接跳过
        if color == 0:
            continue
        # 考虑上下方向
        # 如果比最上边的点更靠上，更新top，即dic[color][0]
        if x < dic[color][0]:
            dic[color][0] = x
        # 如果比最下边的点更靠下，更新bottom，即dic[color][1]
        if x > dic[color][1]:
            dic[color][1] = x
        # 考虑左右方向
        # 如果比最左边的点更靠左，更新left，即dic[color][2]
        if y < dic[color][2]:
            dic[color][2] = y
        # 如果比最右边的点更靠右，更新right，即dic[color][3]
        if y > dic[color][3]:
            dic[color][3] = y

# 计算所有颜色中，最小覆盖面积的最大值
print(max((r-l+1)*(b-t+1) for t, b, l, r in dic.values()))

Java

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int m = scanner.nextInt();
        int n = scanner.nextInt();
        int[][] grid = new int[m][n];

        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                grid[i][j] = scanner.nextInt();
            }
        }

        Map<Integer, int[]> dic = new HashMap<>();

        for (int x = 0; x < m; x++) {
            for (int y = 0; y < n; y++) {
                int color = grid[x][y];
                if (color == 0) {
                    continue;
                }

                if (!dic.containsKey(color)) {
                    dic.put(color, new int[]{Integer.MAX_VALUE, Integer.MIN_VALUE, Integer.MAX_VALUE, Integer.MIN_VALUE});
                }

                int[] boundaries = dic.get(color);

                if (x < boundaries[0]) {
                    boundaries[0] = x;
                }
                if (x > boundaries[1]) {
                    boundaries[1] = x;
                }
                if (y < boundaries[2]) {
                    boundaries[2] = y;
                }
                if (y > boundaries[3]) {
                    boundaries[3] = y;
                }
            }
        }

        int maxArea = 0;
        for (int[] boundary : dic.values()) {
            int top = boundary[0];
            int bottom = boundary[1];
            int left = boundary[2];
            int right = boundary[3];

            int area = (bottom - top + 1) * (right - left + 1);
            maxArea = Math.max(maxArea, area);
        }

        System.out.println(maxArea);
    }
}

C++

“`C++
#include <iostream>
#include <vector>
#include <unordered_map>
#include <algorithm>
#include <climits>

int main() {
int m, n;
std::cin >> m >> n;
std::vector<std::vector<int>> grid(m, std::vector<int>(n));

<pre><code>for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
std::cin >> grid[i][j];
}
}

std::unordered_map<int, std::vector<int>> dic;

for (int x = 0; x < m; x++) {
for (int y = 0; y < n; y++) {
int color = grid[x][y];
if (color == 0) {
continue;
}

if (dic.find(color) == dic.end()) {
dic[color] = {INT_MAX, INT_MIN, INT_MAX, INT_MIN};
}

auto& boundaries = dic[color];

if (x < boundaries[0]) {
boundaries[0] = x;
}
if (x > boundaries[1]) {
boundaries[1] = x;
}
if (y < boundaries[2]) {
boundaries[2] = y;
}
if (y > boundaries[3]) {
boundaries[3] = y;
}
}
}

int maxArea = 0;
for (auto& boundary : dic) {
auto& boundaries = boundary.second;
int top = boundaries[0];
int bottom = boundaries[1];
int left = boundaries[2];
int right = boundaries[3];

int area = (bottom – top + 1) * (right – left + 1);
maxArea = std::max(maxArea, area);
}

std::cout << maxArea << std::endl;

return 0;
</code></pre>

}

“`

时空复杂度

时间复杂度：O(NM)。仅需一次遍历整个grid二维矩阵。

空间复杂度：O(K)。哈希表所占空间，其中K为颜色种类。

说明

华为OD机试有三道题⽬，第⼀道和第⼆道属于简单或中等题，分值为 100 分，第三道为中等或困难题，分值为 200分，总分为 400 分。

机试分数越⾼评级越⾼，⼯资也就越⾼。

关于华为 OD 机试更加详细的介绍可以查看这篇⽂章：华为OD机考须知

关于机考题目汇总可以看这篇文章：华为OD机试真题 2023 A+B+C+D卷 + 2024新卷（Python&Java&C++）⽬录汇总（每⽇更新）

上一篇 【贪心】2023C-分割均衡字符串
下一篇 【贪心】2023C-虚拟游戏理财

相关文章