华为OD统一考试 -分配土地

题目描述

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

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

输入描述

第一行输入 m 和 n,

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

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

输出描述

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

备注

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

用例

输入

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

输入

3 3

1 0 2

0 0 0

0 3 4

输出

1

说明

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

题目解析

根据用例1说明来看,最小矩形需要覆盖相同数字得所有旗子。

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

但是这产生一个问题?比如下图所示:

如果我要覆盖住所有的数字1,那么必然会同时覆盖了数字2,3,此时该怎么办呢?

题目没有说怎么处理,那么我理解就不需要管,只需要保证覆盖所有1的矩形最小就行。

本题解题思路很简单,只需要统计出相同数字的出现的“所有坐标位置”中:

  • 最小的横坐标(矩形最上面一行的行号)
  • 最大的横坐标(矩形最下面一行的行号)
  • 最小的纵坐标(矩形最左边一列的列号)
  • 最大的纵坐标(矩形最右边一列的列号)

即可。比如:前面图示中数字1的所有坐标位置(1,1)、(1,3)、(2,4)、(3,1)、(3,3)中:

  • 最小的横坐标:1
  • 最大的横坐标:3
  • 最小的纵坐标:1
  • 最大的纵坐标:4

那么包含所有数字1的最小矩形面积为:

(最大的横坐标 - 最小的横坐标 + 1) * (最大的纵坐标 - 最小的纵坐标 + 1)

imp

剩余60%内容,订阅专栏后可继续查看/也可单篇购买

2024华为OD机试卷题 文章被收录于专栏

本专栏给大家提供了华为2024最新华为OD 题目汇总。华为OD机试刷题记录机考算法题库,帮助你上岸华为。提供C++/Java、JavaScript、Python四种语言的解法。

全部评论
点赞 回复 分享
发布于 2024-09-21 09:10 四川

相关推荐

02-24 17:39
门头沟学院 Java
神哥不得了:神哥来啦~专业技能的话建议不要前面空那么多,八股的话建议先把高频top 50的八股多巩固几遍,千万不要看那些假高频八股。项目的话,建议换两个高质量的项目上去
点赞 评论 收藏
分享
今天 14:40
浙江大学 设计
无语😓 就喜欢找我茬,研究生怎么了 研究生就是天才吗 就得所有报告文件都会,最烦做表
我推的MK:是这样的,那些领导就是自己什么都不懂就把所有东西扔给你,指望白嫖你的劳动力,如果你的表现不如预期就启动攻击学历模式,这都学不会是怎么考上浙大的
点赞 评论 收藏
分享
评论
1
1
分享

创作者周榜

更多
牛客网
牛客企业服务