OD C卷 - 分配土地
分配土地（100）
- 矩形土地上插上小旗子，旗子上数字从1->500；
- 数值为0表示该土地上没有旗子，土地边长不超过500;
- 将覆盖相同旗子数字的最小矩阵的土地，分配给有贡献的人，最大可以分配多大面积？
输入描述：
第一行输入m,n； m表示土地长，n表示宽；
第二行输入土地的标识；
输出描述：
最大分配的面积
示例1
输入：
3 3
1 0 1
0 0 0
0 1 0
输出：
9
说明：覆盖旗子1的最小矩阵为3*3
示例2
输入：
3 3
1 0 2
0 0 0
0 3 4
输出：
1
示例3
输入：
3 3
2 0 2
0 2 1
3 0 3
输出：
6
思路：
- 记录同一个旗子数字的最大长、宽
- 计算覆盖旗子数字最小矩阵的面积，取最大面积
row, col = list(map(int, input().strip().split()))
matrix = []
for i in range(row):matrix.append(list(map(int, input().strip().split())))# 统计旗子
stats_dict = {}
for i in range(row):for j in range(col):if matrix[i][j]:# 统计当前旗子数字flag = matrix[i][j]if flag not in stats_dict:stats_dict[flag] = [[i, j], [i, j], [0, 0]] # [第一个旗子位置, 最大长宽位置， 长宽间距]else:# 更新stats_dictstart, end, dist = stats_dict[flag]if abs(i - start[0]) > dist[0]:end[0] = idist[0] = abs(i - start[0])if abs(j - start[1]) > dist[1]:end[1] = jdist[1] = abs(j - start[1])#
# 计算面积，并取最大值
max_area = 0
for k, v in stats_dict.items():start, end, _ = vcur_area = (abs(end[0] - start[0]) + 1) * (abs(end[1] - start[1]) + 1)if cur_area > max_area:max_area = cur_areaprint(max_area)
其他解法：
params = [int(x) for x in input().split(" ")]
a = params[0]
b = params[1]
nums = [0 for x in range(501)]
max_row = [0 for x in range(501)]
max_col = [0 for x in range(501)]
min_row = [502 for x in range(501)]
min_col = [502 for x in range(501)]for i in range(a):params = [int(x) for x in input().split(" ")]for j in range(b):c = params[j]nums[c] = 1max_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):c = nums[i]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)