刷题笔记合集🔗

分配土地

问题描述

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

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

输入格式

第一行输入 和 ，

• 代表村子的土地的长
• 代表土地的宽

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

输出格式

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

样例输入

3 3
1 0 1
0 0 0
0 1 0

3 3
1 0 2
0 0 0
0 3 4

样例输出

9

1

数据范围

• 旗子上的数字为
• 土地边长不超过
• 未插旗子的土地用 标识

题解

这道题目要我们为村民分配土地，土地上插着标有数字的旗子。我们需要找出能够覆盖所有相同数字旗子的最小矩形区域，并计算其中面积最大的是多少。

解题思路很直观：统计每种数字的旗子位置，找出它们形成的最小矩形面积，然后取最大值。

具体步骤如下：

1. 读取土地的长宽 m 和 n，以及土地上的标识矩阵
2. 对于每个非零数字，记录它们出现的所有坐标
3. 计算每个数字对应的最小矩形面积
   • 需要找到该数字旗子的最小行、最大行、最小列、最大列
   • 矩形面积 = (最大行 - 最小行 + 1) × (最大列 - 最小列 + 1)
4. 返回所有矩形面积中的最大值

这里的关键在于如何表示每个数字对应的矩形区域。一个高效的方法是用四个变量记录矩形的边界：

• minRow：该数字出现的最小行号
• maxRow：该数字出现的最大行号
• minCol：该数字出现的最小列号
• maxCol：该数字出现的最大列号

时间复杂度是 O(m×n)，因为我们需要遍历整个土地矩阵。空间复杂度是 O(k)，其中 k 是不同数字的数量。对于题目给定的数据范围（土地边长不超过500），这个复杂度完全可以接受。

参考代码

• Python

import sys
input = lambda:sys.stdin.readline().strip()

class Area:
    def __init__(self):
        # 初始化边界值
        self.min_r = float('inf')  # 最小行
        self.max_r = -float('inf')  # 最大行
        self.min_c = float('inf')  # 最小列
        self.max_c = -float('inf')  # 最大列
    
    def update_row(self, r):
        # 更新行的边界
        self.min_r = min(self.min_r, r)
        self.max_r = max(self.max_r, r)
    
    def update_col(self, c):
        # 更新列的边界
        self.min_c = min(self.min_c, c)
        self.max_c = max(self.max_c, c)
        
    def area(self):
        # 计算矩形面积
        return (self.max_r - self.min_r + 1) * (self.max_c - self.min_c + 1)

# 读取输入
m, n = map(int, input().split())
land = []
for _ in range(m):
    land.append(list(map(int, input().split())))

# 记录每个数字的区域边界
flags = {}
for r in range(m):
    for c in range(n):
        val = land[r][c]
        if val > 0:  # 跳过未插旗的位置
            # 如果是新数字，创建新区域
            if val not in flags:
                flags[val] = Area()
            # 更新该数字对应的矩形边界
            flags[val].update_row(r)
            flags[val].update_col(c)

# 计算最大面积
max_area = 0
for val in flags:
    max_area = max(max_area, flags[val].area())

# 如果没有旗子，返回1（单块土地）
if max_are