上次贴的代码不对，这次更新了一下
下载

/**
    滑雪Description
    Time Limit: 1000MS  Memory Limit: 65536K 
    Total Submissions: 27578  Accepted: 9545 
    
    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更长。事实上，这是最长的一条。
    
    Input
    输入的第一行表示区域的行数R和列数C(1 <= R,C <= 100)。下面是R行，每行有C个整数，代表高度h，0<=h<=10000。
    
    Output
    输出最长区域的长度。
    
    Sample Input
    5 5
     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
    
    
    Sample Output
    25
 */
/**
 * 得考虑到有相同高度的点,所以中途应该记录坐标
 * 最高点与最低点可以有多个，但是假设:终点只有一个，就是第一个最低的点。出发点只有一个，第一个最高的点。
 */
public class Skee {
    public int xw,yw;//矩阵的长与宽
    
    //前两维索引是点坐标，最后一维：
    //[0]当前点的高度 [1]是否(1|0)曾到达过该点 [2,3]当前最佳上一点坐标y,x [4]当前到该步为止最佳路径长度 
    //[5,6][7,8][9,10][11,12]分别为上下左右下一步的点的坐标，若为(-1,-1)则该点对应方向不可以走，或者该点还未向四周滑动
    public int[][][] ptInfos;//[y][x][13]    
    //[0] 高度 [1]是1否0己有父坐标 [2,3]当前最远路径父坐标y,x [4]路径长度 [5,6][7,8][9,10][11,12]分别为上下左右下一步坐标
    
    //存储当前轮可以滑动的点以及下一轮可以滑动的点
    //[点数][3] 第二维的三分别为：Index0值:0该点未使用或己作废,1本轮可向四周滑动的点,2本轮新加入的点_下一轮才能向四周滑动 (Index1,Index2)点坐标 
    public int[][] ptNowStep;
    int ptNowStepTop = 0;//当前使用到的位置的顶部，可以理解为栈顶的意思吧
    int ptNowStepIndex;//一个可以利用的存新的未走过的点的位置
    int ptNowStepRecycle = -1;//最后一个回收的点
    
    int Point_StartX, Point_StartY, Point_EndX, Point_EndY;//出发点与终点的坐标
    int xNow, yNow, xNext, yNext, hNow;//当前点的坐标、下一步的坐标、当前点的高度
    boolean canNextStep;//己加入新的未走过的点，需要继续滑
    
    public int[] hightPath;
    
    //pts矩阵，存储各坐标点对应的高度
    public Skee(int[][] pts) {
        yw = pts.length;
        xw = pts[0].length;
        ptInfos = new int[yw][xw][13];
        ptNowStep = new int[yw * xw][3];
        for (int y = 0; y < yw; y++) {
            for (int x = 0; x < xw; x++) {
                ptInfos[y][x][0] = pts[y][x];
                for (int i = 5; i <= 12; i++) {
                    ptInfos[y][x][i] = -1;
                }
            }
        }
        
        //找到出发点与终点
        int valStart = 0, valEnd = 10001;
        for (int y = 0; y < yw; y++) {
            for (int x = 0; x < xw; x++) {
                if (ptInfos[y][x][0] < valEnd) {
                    valEnd = ptInfos[y][x][0];
                    Point_EndX = x;
                    Point_EndY = y;
                } else if (ptInfos[y][x][0] > valStart) {
                    valStart = ptInfos[y][x][0];
                    Point_StartX = x;
                    Point_StartY = y;
                }
            }
        }
        
        //初始化出发点
        ptInfos[Point_StartY][Point_StartX][4] = 1;
        ptNowStepIndex = get_ptNowStepIndex();
        ptNowStep[ptNowStepIndex][0] = 1;
        ptNowStep[ptNowStepIndex][1] = Point_StartY;
        ptNowStep[ptNowStepIndex][2] = Point_StartX;
    }
    
    //开始计算路径
    public void computePath() {
        while(nextStep());
    }
    
    
    //返回最长步数（实际是点数）
    public int getMatStep() {
        return ptInfos[Point_EndY][Point_EndX][4];
    }
    
    //打印出最长步数的所有点高度
    public void printMaxStep() {
        int top = xw*yw - 1;
        int x = Point_EndX;
        int y = Point_EndY;
        int tmp;
        hightPath = new int[xw*yw];
        while (ptInfos[y][x][1] == 1) {
            hightPath[top--] = ptInfos[y][x][0];
            tmp = y;
            y = ptInfos[tmp][x][2];
            x = ptInfos[tmp][x][3];
        }
        hightPath[top--] = ptInfos[y][x][0];
        top++;
        System.out.print(hightPath[top++]);
        for (int i = top; i < hightPath.length; i++) {
            System.out.print("->" + hightPath[i]);
        }
        System.out.println();
    }
    
    //取一个ptNowStep的index用于保存需要扩展的点
    private int get_ptNowStepIndex() {
        if (ptNowStepRecycle != -1) {
            int tmp = ptNowStepRecycle;
            ptNowStepRecycle = -1;
            return tmp;
        }
        for (int i = 0; i < ptNowStep.length; i++) {
            if (ptNowStep[i][0] == 0) {
                if (i >= ptNowStepTop) {
                    ptNowStepTop = i + 1;
                }
                return i;
            }
        }
        return -1;//不会走到，除非程序有问题
    }
    
    private boolean nextStep() {
        int ptNowStepTopTmp = ptNowStepTop;
        canNextStep = false;
        for (int i = 0; i < ptNowStepTopTmp; i++) {
            if (ptNowStep[i][0] != 1) {
                continue;
            } else if (ptNowStep[i][1] == Point_EndY && ptNowStep[i][2] == Point_EndX) {
                ptNowStep[i][0] = 0;
                continue;
            }
            xNow = ptNowStep[i][2];
            yNow = ptNowStep[i][1];
            hNow = ptInfos[yNow][xNow][0];
            //向上滑
            xNext = xNow;
            yNext = yNow - 1;
            if (yNext >= 0 && hNow > ptInfos[yNext][xNext][0]) {
                stepInto(0);
            }
            //向下滑
            yNext = yNow + 1;
            if (yNext < yw && hNow > ptInfos[yNext][xNext][0]) {
                stepInto(1);
            }
            //向左滑
            yNext = yNow;
            xNext = xNow - 1;
            if (xNext >= 0 && hNow > ptInfos[yNext][xNext][0]) {
                stepInto(2);
            }
            //向右滑
            xNext = xNow + 1;
            if (xNext < xw && hNow > ptInfos[yNext][xNext][0]) {
                stepInto(3);
            }
            ptNowStep[i][0] = 0;
            ptNowStepRecycle = i;
        }
        if (canNextStep) {
            for (int i = 0; i < ptNowStepTop; i++) {
                if (ptNowStep[i][0] == 2) {
                    ptNowStep[i][0] = 1;
                }
            }
            return true;
        }
        return false;
    }
    
    //向前滑一步 dir=0123:上下左右
    private void stepInto(int dir) {
        //本步的子指向更新
        ptInfos[yNow][xNow][5 + dir * 2] = yNext;
        ptInfos[yNow][xNow][6 + dir * 2] = xNext;
        if (ptInfos[yNow][xNow][4] >= ptInfos[yNext][xNext][4]) {//可以得到更多的步数，则更新
            //下一步的父指向更新
            ptInfos[yNext][xNext][2] = yNow;
            ptInfos[yNext][xNext][3] = xNow;
            ptInfos[yNext][xNext][4] = ptInfos[yNow][xNow][4] + 1;
            if (ptInfos[yNext][xNext][1] == 1) { //先前己探索，更新子孙路径长度
                updateSubPathLen(yNext, xNext);
            } else {
                ptInfos[yNext][xNext][1] = 1;
                ptNowStepIndex = get_ptNowStepIndex();
                ptNowStep[ptNowStepIndex][0] = 2;
                ptNowStep[ptNowStepIndex][1] = yNext;
                ptNowStep[ptNowStepIndex][2] = xNext;
                canNextStep = true;
            }
        }
    }
    
    //更新后继步的步数
    private void updateSubPathLen(int y, int x) {
        int ysub, xsub;
        int pathLenSub = ptInfos[y][x][4] + 1;
        for (int i = 0; i < 4; i++) {
            ysub = ptInfos[y][x][5 + i * 2];
            xsub = ptInfos[y][x][6 + i * 2];
            if (ysub != -1 && pathLenSub > ptInfos[ysub][xsub][4]) {//可以滑并且可以得到更多的步数，则更新
                ptInfos[ysub][xsub][2] = y;
                ptInfos[ysub][xsub][3] = x;
                ptInfos[ysub][xsub][4] = pathLenSub;
                updateSubPathLen(ysub, xsub);
            }
        }
    }

///以下为测试代码    
//////////////////////////////////////////////////////////////////////////////////////////////
    
    public static void main(String[] args) {
//        {
//            int[][] pts = {
//                    {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}
//            };
//            Skee2 skee = new Skee2(pts);
//            skee.computePath();
//            skee.printMaxStep();
//            System.out.println("最长步数为：" +skee.getMatStep());
//        }
        
        
        {
            int yw = 100, xw = 100;
            boolean isPrintMatrix = false;
            int[][] pts = new int[yw][xw];
            createLuoXuanMatrix(pts, -1, xw, -1, yw, 0, 0, 0, 0);

            if (isPrintMatrix) {
                System.out.println("螺旋矩阵：");
                int formatLen = Integer.toString(yw * yw -1).length();
                for (int y = 0; y < yw; y++) {
                    for (int x = 0; x < xw; x++) {
                        System.out.print(getNSpace(formatLen-Integer.toString(pts[y][x]).length()) + pts[y][x] + " ");
                    }
                    System.out.println();
                }
                System.out.println("----- End Matrix -----\n");
            }
            
            long time = System.currentTimeMillis();
            
            Skee skee = new Skee(pts);
            skee.computePath();
            //skee.printMaxStep();
            System.out.println("最长步数为：" +skee.getMatStep());
            
            System.out.println();
            System.out.println("总时间：" + (System.currentTimeMillis() - time));
        }
    }
    
    
    
    ///创建螺旋矩阵
    //用于产生螺旋数矩阵
    public static void createLuoXuanMatrix(int[][] pts, int xMin, int xMax, int yMin, int yMax, int dir, int now, int x, int y) {
        switch (dir) {
            case 0://向右
                if (xMin >= xMax) {
                    return;
                }
                while (x < xMax) {
                    pts[y][x++] = now++;
                }
                x--;
                now--;
                yMin++;
                break;
            case 1://向下
                if (yMin >= yMax) {
                    return;
                }
                while (y < yMax) {
                    pts[y++][x] = now++;
                }
                y--;
                now--;
                xMax--;
                break;
            case 2://向左
                if (xMin >= xMax) {
                    return;
                }
                while (x > xMin) {
                    pts[y][x--] = now++;
                }
                x++;
                now--;
                yMax--;
                break;
            case 3://向上
                if (yMin >= yMax) {
                    return;
                }
                while (y > yMin) {
                    pts[y--][x] = now++;
                }
                y++;
                now--;
                xMin++;
                break;
            default:
                break;
        }
        dir = (dir + 1) % 4;
        createLuoXuanMatrix(pts, xMin, xMax, yMin, yMax, dir, now, x, y);
    }
    public static String getNSpace(int count) {
        return "          ".substring(0, count);
    }
}