java 链队列求解迷宫

链队列是一种使用链表实现的队列数据结构。它具有队列的基本操作，如进队、出队、判断队空和求队中元素个数等。在求解迷宫问题时，可以使用链队列来实现路径的搜索和记录。

以下是使用Java实现链队列求解迷宫的示例代码：

import java.util.LinkedList;
import java.util.Queue;

public class MazeSolver {
    private static final int[][] DIRECTIONS = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}}; // 上下左右四个方向

    public static void solveMaze(int[][] maze, int startX, int startY, int endX, int endY) {
        int rows = maze.length;
        int cols = maze[0].length;
        boolean[][] visited = new boolean[rows][cols]; // 记录每个位置是否已经访问过
        int[][] prev = new int[rows][cols]; // 记录每个位置的前驱位置，用于最后回溯路径

        Queue<int[]> queue = new LinkedList<>(); // 使用链队列存储待访问的位置
        queue.offer(new int[]{startX, startY});
        visited[startX][startY] = true;

        while (!queue.isEmpty()) {
            int[] curr = queue.poll();
            int currX = curr[0];
            int currY = curr[1];

            if (currX == endX && currY == endY) {
                break; // 找到终点，结束搜索
            }

            for (int[] direction : DIRECTIONS) {
                int nextX = currX + direction[0];
                int nextY = currY + direction[1];

                if (nextX >= 0 && nextX < rows && nextY >= 0 && nextY < cols
                        && maze[nextX][nextY] == 0 && !visited[nextX][nextY]) {
                    queue.offer(new int[]{nextX, nextY});
                    visited[nextX][nextY] = true;
                    prev[nextX][nextY] = currX * cols + currY; // 记录前驱位置
                }
            }
        }

        if (!visited[endX][endY]) {
            System.out.println("No path found."); // 没有找到路径
            return;
        }

        // 回溯路径
        int currX = endX;
        int currY = endY;
        while (currX != startX || currY != startY) {
            int prevX = prev[currX][currY] / cols;
            int prevY = prev[currX][currY] % cols;
            maze[currX][currY] = 2; // 标记路径
            currX = prevX;
            currY = prevY;
        }
        maze[startX][startY] = 2; // 标记起点
        maze[endX][endY] = 2; // 标记终点

        // 打印迷宫和路径
        for (int[] row : maze) {
            for (int cell : row) {
                if (cell == 0) {
                    System.out.print("□ "); // 未访问的位置
                } else if (cell == 1) {
                    System.out.print("■ "); // 墙壁
                } else {
                    System.out.print("★ "); // 路径
                }
            }
            System.out.println();
        }
    }
}

使用上述代码，可以通过调用`solveMaze`方法来求解迷宫。其中，`maze`是一个二维数组表示迷宫，0表示可通行的位置，1表示墙壁，`startX`、`startY`表示起点的坐标，`endX`、`endY`表示终点的坐标。