最长的滑道 .
问题：
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个点进行遍历，而是只对“没有被路径扫过的点”或者说“级别为零”的点进行遍历。
?
稍后我附上自己的程序实现，请大家参考和讨论。
欢迎大家踊跃讨论和拍砖！！
?
1 楼 freebird0221 2012-03-20 起点的选择好像不对，比如