java数据结构与算法之马踏棋盘

本文实例为大家分享了java数据结构与算法之马踏棋盘的具体代码，供大家参考，具体内容如下

• 马踏棋盘算法也被称为骑士周游问题
• 将马随机放在过期象棋的8x8棋盘的某个方格中，马按走棋规则进行移动，要求每个方格只进入一次，走遍棋盘上全部64个方格

骑士周游问题结局步骤和思路

1.创建棋盘chessBoard，是一个二维数组
2.将当前位置设置为已个访问，然后根据当前位置，计算马儿还能走那些位置，并放到一个集合中(ArrayList)，最多8个位置
3.变量ArrayList存放的所有位置，看看哪个可以走通
4.判断马儿是否完成了骑士周游问题

注意：马儿不同的走法，会得到不同的结果，效率也会有影响

代码实现

public class HorseChessBoard {

    private static int X;  //棋盘的列数
    private static int Y;  //棋盘的行数
    
    //创建数组标记棋盘各个位置是否被访问过
    private static boolean[] visited;
    //使用一个属性标记是否棋盘的所有位置都被访问过，即是否成功
    private static boolean finish;  //如果为true表示成功
    
    public static void main(String[] args) {
        X = 8;
        Y = 8;
        int row = 1;
        int col = 1; 
        int[][] chessboard =  new int[X][Y];
        visited = new boolean[X * Y];
        
        long start = System.currentTimeMillis();
        traversalChessboard(chessboard, row-1, col-1, 1);
        long end = System.currentTimeMillis();
        System.out.println(end - start);
        
        for (int[] rows : chessboard) {
            for (int step : rows) {
                System.out.print(step + "  ");
            }
            System.out.println();
        }
    }
    
    //其实周游问题
    public static void traversalChessboard(int[][] chessboard, int row, int col, int step) {
        
        if (finish) return;
        chessboard[row][col] = step;
        visited[row * X + col] = true;  //标记该位置已经访问
        //获取当前位置可以走的下一个位置的集合
        List<Point> ps = next(new Point(col, row));
        sort(ps);
        
        //遍历ps
        while (!ps.isEmpty()) {
            Point p = ps.remove(0);  //取出下一个可以走的位置
            //判断该点是否已经访问过
            if (!visited[p.y * X + p.x]) {
                traversalChessboard(chessboard, p.y, p.x, step+1);
            }
        }
        
        //1. 棋盘到目前位置任然未走完
        //2. 棋盘处于一个回溯过程
        if (step < X * Y && !finish) {
            chessboard[row][col] = 0;
            visited[row * X + col] = false;
        } else {
            finish = true;
        }
    }
    
    //根据当前这一步的所有的下一步的选择位置进行非递减排序
    public static void sort(List<Point> ps) {
        ps.sort(new Comparator<Point>() {

            @Override
            public int compare(Point o1, Point o2) {
                //获取o1,o2下一步所有个数
                int count1 = next(o1).size();
                int count2 = next(o2).size();
                if (count1 < count2) {
                    return -1;
                } else if (count1 == count2) {
                    return 0;
                } else {
                    return 1;
                }
            }
        });
    }
    
    //Point:根据当前位置(point对象)
    //根据当前位置，计算马儿还能走那些位置，并放到一个集合中(ArrayList)，最多8个位置
    public static List<Point> next(Point curPoint) {
        //创建list集合
        List<Point> ps = new ArrayList<>();
        //创建一个point
        Point p1 = new Point();
        if ((p1.x = curPoint.x-2) >= 0 && (p1.y = curPoint.y-1) >= 0) {
            ps.add(new Point(p1));
        }
        
        if ((p1.x = curPoint.x-1) >= 0 && (p1.y = curPoint.y-2) >= 0) {
            ps.add(new Point(p1));
        }
        
        if ((p1.x = curPoint.x+1) < X && (p1.y = curPoint.y-2) >= 0) {
            ps.add(new Point(p1));
        }
        
        if ((p1.x = curPoint.x+2) < X && (p1.y = curPoint.y-1) >= 0) {
            ps.add(new Point(p1));
        }
        
        if ((p1.x = curPoint.x+2) < X && (p1.y = curPoint.y+1) < Y) {
            ps.add(new Point(p1));
        }
        
        if ((p1.x = curPoint.x+1) < X && (p1.y = curPoint.y+2) < Y) {
            ps.add(new Point(p1));
        }
        
        if ((p1.x = curPoint.x-1) >= 0 && (p1.y = curPoint.y+2) < Y) {
            ps.add(new Point(p1));
        }
        
        if ((p1.x = curPoint.x-2) >= 0 && (p1.y = curPoint.y+1) < Y) {
            ps.add(new Point(p1));
        }
        
        return ps;
    }

}

以上就是本文的全部内容，希望对大家的学习有所帮助，也希望大家多多支持我们。