问题:
Michael喜欢滑雪百这并不奇怪, 因为滑雪的确很刺激。可是为了获得速度,滑的区域必须向下倾斜,而且当你滑到坡底,你不得不再次走上坡或者等待升降机来载你。Michael想知道一个区域中最长的滑坡。区域由一个二维数组给出。数组的每个数字代表点的高度。下面是一个例子
1 2 3 4 5
16 17 18 19 6
15 24 25 20 7
14 23 22 21 8
13 12 11 10 9
一个人可以从某个点滑向上下左右相邻四个点之一,当且仅当高度减小。在上面的例子中,一条可滑行的滑坡为24-17-16-1。当然25-24-23-…-3-2-1更长。事实上,这是最长的一条,长度是25。
我的思路,从最低位置向上寻找路径,为途径的所有位置标注地势级别值,直到所有路径标识完毕,从地势级别值最高的开始回归出最长的路径,具体如下,
a. 假设原始的区域数组为zone[5][5],新建一个二维数组paths[5][5]存路径;
b. 将N^2个位置进行排序,得到升序的数组dots[25],每个元素存储该位置的横纵坐标,复杂度O(NlgN);
c. 初始化paths[dots[0].x][dots[0].y]=0,遍历dots[i=0],
c.1 用一个链表list记录要标识的位置,先加入dots[i];
c.2 遍历list列表,
{
从list里面读出一个位置temp,读取temp在zone中周围四个位置的高度值,比如zone[x][y],其中x=temp.x + 1,y=temp.y,如果zone[x][y]大于temp对应的高度,那么进行下面的赋值:paths[x][y]=max(paths[x][y], path[temp.x][temp.y]+1),并且把zone[x][y]对应的位置加入到list里面;
}
c.3 i++,返回到c去遍历下一个dots[i];
d. 遍历完所有的dots后,paths中已经存储了最长的那条路径,
d.1 找到paths中的最大值对应的位置paths[mx][my],并把这个最大值赋给变量M;
d.2 输出zone[mx][my]的值,M=M-1,如果M为-1则算法结束;
d.3 在paths[mx][my]的周围四个位置上找到值为M的位置(任意一个都行,比如是paths[mx-1][my],没有的话说明程序出问题了),更新mx和my为新位置(比如mx=mx-1,my=my),执行d.2;
正确性分析,从最低位置开始遍历,找到从该点出发的所有路径并且标记路径长度,这样当遍历较高位置的时候,就可以排除更低点造成的干扰,从而得到准确的路径长度。所以最后paths中的最大值就是路径最长的长度。而向下寻找路径的时候,因为这个最长的路径一定是从某个低位逐步加一得到的,所以不断寻找地势级别减一的位置,就能够确定这条路径。
复杂度分析,如果前面的排序需要O(N)的空间复杂度和O(NlgN)的时间复杂度,其中N为位置的个数,后面的遍历比较复杂,最坏的复杂度大概是一个等比数列的求和(指数级!!),最后的确定路径应该还好,基本不到O(N)。
//==================2012.3.26,一点更正
感谢一楼freebird0221的提问,让我重新思考了这个问题。原来想的确实不够具体,有不对的地方。特此更正一下。
我的思路还是那样,先要按照地势排序所有的N^2个位置(我回答freebird0221的说法有误),然后从最低点开始遍历上文提到的那个级别更新过程,但是这里有个地方需要改动:并不是对所有的N^2个点进行遍历,而是只对“没有被路径扫过的点”或者说“级别为零”的点进行遍历。
稍后我附上自己的程序实现,请大家参考和讨论。
欢迎大家踊跃讨论和拍砖!!
//===============================重读后,结合示例,整理了一遍思路
a. 从最低点开始,zone[0][0]=1,标注周围点的高度级别,
1(0) 2(1) 3 4 5
16(1) 17 18 19 6
15 24 25 20 7
14 23 22 21 8
13 12 11 10 9
b. 遍历刚刚被标注的位置,标注该位置周围点的高度级别,直到没有新标注的位置
1(0) 2(1) 3(2) 4(3) 5(4)
16(15) 17(16) 18(17) 19(18) 6 (5)
15(14) 24(23) 25(24) 20(19) 7 (6)
14(13) 23(22) 22(21) 21(20) 8 (7)
13(12) 12(11) 11(10) 10(9) 9 (8)
c. 该例子下,0级别的位置只有一个。通常可能有多个,多个的情况下重新从一个0级别的位置执行a、b、c
d. 遍历完所有的0级别点以后,从级别最高的点开始找连续路径,就得到了最长的滑雪路径(25-24-23-22-21-…-4-3-2-1)
1(0) 2(1) 3(2) 4(3) 5(4)
16(15) 17(16) 18(17) 19(18) 6 (5)
15(14) 24(23) 25(24) 20(19) 7 (6)
14(13) 23(22) 22(21) 21(20) 8 (7)
13(12) 12(11) 11(10) 10(9) 9 (8)
相关推荐
油隔离泥浆泵减速箱_十字头_滑道孔磨损后的补修方法.rar
贝勒煤矿地质条件极其复杂,为了缩短工作面回撤与安装时间,将传统的装车搬运方式改为在自制滑道上直接拖运设备的方式,实现综采支架整体快速转运,节省进空车、装车、卸车、出空车工序所需时间,避免了原回撤与安装工艺...
滑道6.SLDPRT.sldprt
介绍了综采工作面电缆自移滑道的设计。包括滑道的结构组成、设计要点、工作原理等。该自移滑道实现了工作面电缆的自动收放,克服了传统煤矿井巷作业时工作面电缆需用吊挂锚杆悬挂而消耗大量人力、物力打吊挂锚杆,人工...
对气动振动式锚杆钻机进行改造,通过加在锚杆钻机上的滑轮将锚杆机固定在特制的滑道上,气缸伸缩,锚杆钻机在滑道上滑动实现钻进,为掘进巷道施工短探,提供了更具操作性的机具,技术经济效益显著。
滑道式提升机及其控制电路的设计.zip滑道式提升机及其控制电路的设计.zip
行业分类-电子-一种滑道式的供电结构
滑道式提升机及其控制电路的设计(1).zip滑道式提升机及其控制电路的设计(1).zip滑道式提升机及其控制电路的设计(1).zip
行业分类-设备装置-滑道式探测定位仪.zip
号滑道码头改造工程施工组织设计.docx
某工作面铺设滑道安全技术措施.docx
电子政务-带导电轨的滑道.zip
电信设备-流水作业可调托盘滑道.zip
近年来,随着煤矿文明生产的加强和机械化程度的提高,煤矿井巷掘进作业时小铲车的使用已日渐增加,其方便...因此,自主研发了掘进工作面小铲车电缆自移滑道装置。该装置结构简单、安装方便、实用性强,投入使用后效果良好。
H3C LSVM1BSR10可伸缩式滑道的最大承重能力为200KG。当承受重量小于100KG时,滑道的伸缩范围为630mm~900mm。当承受重量大于等于10 0 KG时,滑道的伸缩范围为630mm~850mm。安装滑道到机柜前,请确保机柜前后方孔条...
行业文档-设计装置-带粉笔滑道的半圆尺.zip
电信设备-具有移动段的娱乐滑道.zip
基于Matlab的U形滑道曲线的设计.pdf
行业资料-交通装置-一种上滑道车库门轨道.zip
行业分类-设备装置-一种滑道可调距的图书架.zip