华为OD机试真题-分配土地-Python-OD统一考试（C卷）

「爱情、让人受尽委屈。」 2024-02-05 23:55 137阅读 0赞

> **题目描述：**
> 
> 从前有个村庄，村民们喜欢在各种田地上插上小旗子，旗子上标识了各种不同的数字。某天集体村民决定将覆盖相同数字的最小矩阵形的土地的分配给为村里做出巨大贡献的村民，请问，此次分配土地，做出贡献的村民中最大会分配多大面积？
> 
> 输入描述：
> 
> 第一行输入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，即一块土地的面积。  
>

import re
     
    def allocate_land():
        a, b = map(int, input().split())
        nums = [0] * 501
        max_row = [0] * 501
        max_col = [0] * 501
        min_row = [502] * 501
        min_col = [502] * 501
        
        for i in range(a):
            for j in range(b):
                c = int(input())
                nums[c] = 1
                max_row[c] = max(max_row[c], i)
                max_col[c] = max(max_col[c], j)
                min_row[c] = min(min_row[c], i)
                min_col[c] = min(min_col[c], j)
        
        max_area = 0
        for i in range(1, 501):
            if nums[i] == 1:
                max_area = max(max_area, (max_row[i] - min_row[i] + 1) * (max_col[i] - min_col[i] + 1))
        
        print(max_area)
     
    allocate_land()