数据结构与算法之骑士遍历

Question

 public class KnightNode {

    private int x;
    private int y;

    public KnightNode(int x,int y){
        this.x = x;
        this.y= y;
    }

    public int getX() {
        return x;
    }

    public void setX(int x) {
        this.x = x;
    }

    public int getY() {
        return y;
    }

    public void setY(int y) {
        this.y = y;
    }
}

 public class KnightTravels_2 {
    //row和col表示某个坐标走“日”的八个方向
    private static int row[] = {-2,-1,1,2,2,1,-1,-2};
    private static int col[] = {1,2,2,1,-1,-2,-2,-1};
    //每行数据表示一个坐标的8个方向是否有访问过。
    private boolean visited[][] = new boolean[64][8];
    //存储走过的位置
    public LinkedList list = new LinkedList();
    //8*8的棋盘
    protected int[][] matrix = new int[8][8];
    protected int step = 1;
    //x,y表示初始结点
    public void travel(int x,int y){
        while(step < 64){
            int newX = x;
            int newY = y;
            boolean hasNext = false;//标志当前位置(x,y)是否可以找到下一个位置
            for(int i = 0;i < 8;i++){
                newX = x + row[i];
                newY = y + col[i];
                if(newX >= 0 && newX < 8 && newY >= 0 && newY < 8 && !visited[step-1][i] && matrix[newX][newY] == 0){
                    //符合条件：在边界内，且没有访问过
                    //如果可以找到符合条件的下一位置，就将当前位置压入链表，并设置找到的下一位置为当前位置
                    list.add(new KnightNode(x,y));
                    visited[step-1][i] = true;
                    matrix[x][y] = step++;
                    hasNext = true;
                    x = newX;
                    y = newY;
                    break;
                }
                visited[step-1][i] = true;
            }
            if(!hasNext && !list.isEmpty()){
                //如果找不到，就拿到栈顶的元素，从之前找过的方向开始找下一位置，
                matrix[x][y] = 0;
                KnightNode last = (KnightNode) list.getLast();
                x = last.getX();
                y = last.getY();
                list.removeLast();
                visited[step-1] = new boolean[8];
                step--;
            }
        }
    }

    public static void main(String args[]){
        KnightTravels_2 travel = new KnightTravels_2();
        //travel.travel(0,0);
        travel.travel(6,7);
        for(int i = 0;i < travel.matrix.length;i++){
            for(int j = 0;j < travel.matrix[i].length;j++){
                System.out.print(String.format("%4d",travel.matrix[i][j]));
            }
            System.out.println();
        }
    }   
}

大家看看有什么问题，为什么执行效率很差，执行的开始位置是(0,0)时可以打印出结果，但是进入while方法几百万次，其他开始位置陷入了无限循环，不知道是真的需要这么久，还是有个死循环在里面。

Answer 1

http://blog.csdn.net/jarelzhou/article/details/18557949