Java代码实现用队列解决骑士游历问题

骑士游历问题是指在一个 n x n 的棋盘上，给定一个起始位置和一个终点位置，求出骑士从起始位置出发到达终点位置所经过的最短路径。

队列可以用来实现广度优先搜索算法，解决骑士游历问题。具体实现可以参考以下Java代码：

import java.util.*;

public class KnightTour {

    private static final int SIZE = 8; // 棋盘大小
    private static final int[][] DIRECTIONS = {{-2, -1}, {-2, 1}, {-1, -2}, {-1, 2}, {1, -2}, {1, 2}, {2, -1}, {2, 1}}; // 骑士可以走的8个方向

    public static void main(String[] args) {
        int[][] board = new int[SIZE][SIZE]; // 棋盘
        int startX = 0; // 起始位置的x坐标
        int startY = 0; // 起始位置的y坐标
        int endX = 7; // 终点位置的x坐标
        int endY = 7; // 终点位置的y坐标
        int stepCount = bfs(board, startX, startY, endX, endY); // 使用广度优先搜索算法求解最短路径
        System.out.println("骑士从 (" + startX + "," + startY + ") 到 (" + endX + "," + endY + ") 的最短路径为：" + stepCount + " 步");
    }

    /**
     * 使用广度优先搜索算法求解骑士从起始位置到达终点位置所经过的最短路径
     *
     * @param board 棋盘
     * @param startX 起始位置的x坐标
     * @param startY 起始位置的y坐标
     * @param endX 终点位置的x坐标
     * @param endY 终点位置的y坐标
     * @return 骑士从起始位置到达终点位置所经过的最短路径
     */
    private static int bfs(int[][] board, int startX, int startY, int endX, int endY) {
        Queue<int[]> queue = new LinkedList<>();
        queue.offer(new int[]{startX, startY}); // 将起始位置加入队列
        board[startX][startY] = 1; // 标记起始位置已经访问过
        while (!queue.isEmpty()) {
            int[] curr = queue.poll();
            int currX = curr[0]; // 当前位置的x坐标
            int currY = curr[1]; // 当前位置的y坐标
            if (currX == endX && currY == endY) { // 如果当前位置是终点位置，则返回当前位置的步数
                return board[currX][currY] - 1;
            }
            for (int[] direction : DIRECTIONS) {
                int nextX = currX + direction[0]; // 下一个位置的x坐标
                int nextY = currY + direction[1]; // 下一个位置的y坐标
                if (nextX >= 0 && nextX < SIZE && nextY >= 0 && nextY < SIZE && board[nextX][nextY] == 0) { // 如果下一个位置在棋盘范围内且未访问过
                    board[nextX][nextY] = board[currX][currY] + 1; // 标记下一个位置已经访问过，并记录步数
                    queue.offer(new int[]{nextX, nextY}); // 将下一个位置加入队列
                }
            }
        }
        return -1; // 如果无法到达终点位置，则返回-1
    }
}

在上面的代码中，我们使用一个二维数组 `board` 来表示棋盘，其中 `board[i][j]` 的值表示骑士从起始位置到达位置 `(i,j)` 所经过的步数。初始时，我们将起始位置的步数设为1，未访问过的位置的步数设为0。在广度优先搜索算法中，我们使用一个队列 `queue` 来存储待访问的位置。每次从队列中取出一个位置，然后依次将其可达的位置加入队列中，并标记已经访问过的位置的步数，直到找到终点位置或者队列为空为止。最后返回终点位置的步数即可。