小W挖宝藏题解

注:点击标题即可查看原题

NO.1 题意解析

平台上有N*M个地块 , 每个地块都高度不等但都有一个宝藏 , 小w只能可以选择任意一个地块作为起点,也只能从高的地块爬到低的相邻地块(相等高度也爬不过去,相邻指的是上下左右),而不能向比所在地块高的地块爬 , 而小W身上的卫星电话电量只够他打一次电话呼叫救援的 , 小W想知道他应该跳到哪个地块上才能保证在呼叫救援之前在悬浮平台中能捡到最多的宝藏 。区域由一个二维数组给出。数组的每个数字代表地块的高度h ** 数据范围: 1≤n,m≤100, h≤10^7

NO.2 思路解析

题目大致就是让小W从高往低走,输出一条能走的最远的道路就行了,很多人第一眼都会想到贪心,找到最高的平台,往四周选相邻四个平台最高的跳,但是仔细一想就会发现不对,因为平台最高的路线不一定是宝藏最多的路线,比如以下

5    6
18   17   16   15   14
01   01   01   01   13
02   01   99   01   12
03   01   90   01   11
04   01   01   01   10
05   06   07   08   09

如果是用贪心来算的话,第一步就会在99上面,第二步又只会在98上,直到第三步只能到1上面了,只拿了3个宝藏,可实际上智商正常的人都会选择先从18开始,然后跳17,16,15,14.....最后跳到1,这样就可以正整整拿到18个宝藏,是刚刚的6倍多。

样例一眼就能看出答,那又怎么做呢?由于数据范围很小,所以可以用搜索

比如下面这一个例子:

5   6   7   8
4   0   0   0
3   0   9   8
2   1   0   7

以上面这一个例子举例,先从上往下枚举,比如枚举到8,这时可以先判断一下四个方向有哪几个方向能走,将这一个点标记,并向那些能走的方位进发,直到无路可走,返回最大值,再在主函数进行比较就行了

制作不易,感谢观看,欢迎留言