分配土地（C语言）_从前有个村庄,村民们喜欢在备种田地上插上小旗子,旗子上标识了各种不同的数字

题目来自于博主算法大师的专栏：最新华为OD机试C卷+AB卷+OJ（C++JavaJSPy） https://blog.csdn.net/banxia_frontend/category_12225173.html

题目描述

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

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

输入描述

第一行输入 m 和 n，

m 代表村子的土地的长
n 代表土地的宽
第二行开始输入地图上的具体标识

输出描述

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

备注

旗子上的数字为1~500，土地边长不超过500

未插旗子的土地用0标识

用例1

输入

3 3
1 0 1
0 0 0
0 1 0
1
2
3
4

输出

9
1

说明

土地上的旗子为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
2
3
4

输出

1
1

说明

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

解题思路

1. 读取输入：首先读取村庄土地的长 m 和宽 n，以及对应的地图信息（每个格子上的旗子编号）存储在二维数组 land 中。

2. 初始化结构体数组：定义一个结构体 Pos 用于记录每个不同编号旗子所覆盖的矩形区域范围。创建一个大小为 MAX 的 Pos 结构体数组 pos，并将所有元素的坐标值初始化为 -1，表示尚未找到该编号的旗子。

3. 遍历地图更新位置信息：通过两层循环遍历整个地图，对于每个非零旗子编号（即有旗子的位置），根据其横纵坐标更新或初始化对应编号在 pos 数组中的矩形区域范围。

4. 计算最大面积：初始化一个变量 maxArea 用于存储当前已知的最大面积。再次遍历 pos 数组，检查是否存在对应编号的旗子（min_x != -1）。如果存在，则计算该编号旗子所覆盖矩形区域的面积，并与当前最大面积进行比较。若新面积大于已知最大面积，则更新最大面积。

5. 输出结果：最后输出此次分配土地中，做出贡献的村民所能获得的最大面积。

代码

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

// 定义一个常量MAX，用于表示旗子编号的最大值（此处应该移除分号）
#define MAX 501 // 此处注释：定义的宏常量代表旗子最大编号，根据题目描述，应为500而不是501

// 定义一个结构体Pos，用来存储每个旗子编号对应的矩形区域范围
typedef struct {
    int min_x, min_y; // 分别表示当前数字在地图上的最小横纵坐标
    int max_x, max_y; // 分别表示当前数字在地图上的最大横纵坐标
} Pos;

int main() {
    // 读取村庄土地的长m和宽n
    int m, n;
    scanf("%d %d", &m, &n);

    // 初始化二维数组land来存储土地上各个位置的旗子编号
    int land[m][n];

    // 读取地图上每个位置的旗子标识
    for (int i = 0; i < m; i++) {
        for (int j = 0; j < n; j++) {
            scanf("%d", &land[i][j]);
        }
    }

    // 初始化一个Pos类型的数组pos，用于记录每个旗子编号所覆盖的矩形区域范围
    Pos pos[MAX];
    memset(pos, -1, sizeof(pos)); // 使用memset将所有元素的min_x、min_y、max_x、max_y初始化为-1，表示尚未找到该编号的旗子

    // 遍历整个地图，更新每个编号对应的位置信息
    for (int i = 0; i < m; i++) {
        for (int j = 0; j < n; j++) {
            int num = land[i][j]; // 当前遍历到的旗子编号
            if (num != 0) { // 如果当前位置有旗子（非0标识）
                // 如果是第一次遇到此编号，则初始化其矩形区域范围
                if (pos[num].min_x == -1) {
                    pos[num].min_x = pos[num].max_x = i;
                    pos[num].min_y = pos[num].max_y = j;
                } else {
                    // 更新当前编号矩形区域范围的边界
                    if (i < pos[num].min_x)
                        pos[num].min_x = i;
                    if (i > pos[num].max_x)
                        pos[num].max_x = i;
                    if (j < pos[num].min_y)
                        pos[num].min_y = j;
                    if (j > pos[num].max_y)
                        pos[num].max_y = j;
                }
            }
        }
    }

    // 初始化最大面积变量
    int maxArea = 0;

    // 遍历所有可能的旗子编号（从1开始），计算并更新最大面积
    for (int num = 1; num < MAX; num++) {
        // 检查是否有找到过对应编号的旗子
        if (pos[num].min_x != -1) {
            // 计算当前编号旗子覆盖的矩形区域的面积
            int area = (pos[num].max_x - pos[num].min_x + 1) * 
                       (pos[num].max_y - pos[num].min_y + 1);
            
            // 如果当前面积大于已知最大面积，则更新最大面积
            if (area > maxArea) {
                maxArea = area;
            }
        }
    }

    // 输出此次分配土地中，做出贡献的村民所能获得的最大面积
    printf("%d\n", maxArea);

    return 0; // 程序正常结束
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79