最长的滑道

问题：

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)

评论

2 楼 peizhyi 2012-03-24  

freebird0221 写道

起点的选择好像不对，比如

  1   6   2 12 13
  8   7   3 21 16
  4   5   6 20 19
18 17 15 14 22
23   9 10 24 25

我试试哈，先从1开始，找一遍路径以后得到：

1(0)    6(1)    2( )  12( )  13( )
8(1)    7(2)    3( )  21( )  16( )
4( )    5( )    6( )  20( )  19( )
18( )  17( )   15( )  14( )  22( )
23( )   9( )   10( )  24( )  25( )

找2以后，

1(0)    6(1)    2(0)  12(1)  13(2)
8(1)    7(2)    3(1)  21(6)  16(3)
4( )    5( )    6(2)  20(5)  19(4)
18(5)  17(4)   15(3)  14( )  22(5)
23(6)   9( )   10( )  24( )  25(6)

后面的也是一样，每个点的级别不会降低，遍历完所有节点后，每个点对应的级别都是其能达到的最高级别，也就是能滑下去的最远距离。

我前面的排序应该是多余了，遍历时谁先谁后对结果是没有影响的。有可能排序以后执行的效率能高点，不过也不一定，需要再多想想。你看看我说的对不？欢迎讨论。

1 楼 freebird0221 2012-03-20  

起点的选择好像不对，比如

  1   6   2 12 13
  8   7   3 21 16
  4   5   6 20 19
18 17 15 14 22
23   9 10 24 25