寻找迷宫最短路径，如何用java实现

寻找迷宫最短路径可以用广度优先搜索（BFS）来实现。BFS 从起点开始，逐层向外扩展搜索，直到找到终点或者搜索完所有可达点。在搜索过程中，需要记录每个点的距离和前驱节点，以便找到最短路径。

下面是用 BFS 实现寻找迷宫最短路径的大致步骤：

1. 定义一个队列，将起点入队。
2. 定义一个二维数组，记录每个点是否被访问过，并初始化为 false。
3. 定义一个二维数组，记录每个点的距离和前驱节点，并初始化为 -1 和 null。
4. 从队列中取出一个点，将其标记为已访问。
5. 遍历该点的所有邻居，如果邻居没有被访问过，则将其入队，并更新距离和前驱节点。
6. 如果终点被标记为已访问，则找到了最短路径，可以根据前驱节点数组回溯路径。

下面是一个简单的 Java 代码实现：

import java.util.*;

public class ShortestPath {
    static int[][] dirs = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}}; // 上下左右四个方向

    public static List<int[]> bfs(char[][] maze, int[] start, int[] end) {
        int m = maze.length, n = maze[0].length;
        boolean[][] visited = new boolean[m][n];
        int[][] distance = new int[m][n];
        int[][] prev = new int[m][n];
        for (int i = 0; i < m; i++) {
            Arrays.fill(distance[i], -1);
            Arrays.fill(prev[i], -1);
        }
        Queue<int[]> queue = new LinkedList<>();
        queue.offer(start);
        visited[start[0]][start[1]] = true;
        distance[start[0]][start[1]] = 0;

        while (!queue.isEmpty()) {
            int[] cur = queue.poll();
            for (int[] dir : dirs) {
                int ni = cur[0] + dir[0], nj = cur[1] + dir[1];
                if (ni >= 0 && ni < m && nj >= 0 && nj < n && maze[ni][nj] != '#' && !visited[ni][nj]) {
                    visited[ni][nj] = true;
                    distance[ni][nj] = distance[cur[0]][cur[1]] + 1;
                    prev[ni][nj] = cur[0] * n + cur[1];
                    if (ni == end[0] && nj == end[1]) {
                        return getPath(prev, start, end, n);
                    }
                    queue.offer(new int[]{ni, nj});
                }
            }
        }

        return new ArrayList<>();
    }

    private static List<int[]> getPath(int[][] prev, int[] start, int[] end, int n) {
        List<int[]> path = new ArrayList<>();
        int cur = end[0] * n + end[1];
        while (cur != start[0] * n + start[1]) {
            int pi = cur / n, pj = cur % n;
            path.add(new int[]{pi, pj});
            cur = prev[pi][pj];
        }
        path.add(start);
        Collections.reverse(path);
        return path;
    }

    public static void main(String[] args) {
        char[][] maze = {
                {'#', '#', '#', '#', '#', '#', '#', '#', '#', '#'},
                {'#', ' ', ' ', ' ', '#', ' ', ' ', ' ', ' ', '#'},
                {'#', ' ', ' ', ' ', '#', ' ', ' ', ' ', ' ', '#'},
                {'#', ' ', ' ', ' ', '#', ' ', ' ', ' ', ' ', '#'},
                {'#', ' ', ' ', ' ', ' ', ' ', '#', '#', ' ', '#'},
                {'#', ' ', '#', '#', '#', '#', ' ', ' ', ' ', '#'},
                {'#', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', '#'},
                {'#', '#', '#', '#', '#', '#', '#', '#', '#', '#'},
        };
        int[] start = {1, 1};
        int[] end = {6, 8};
        List<int[]> path = bfs(maze, start, end);
        System.out.println("最短路径：");
        for (int[] p : path) {
            System.out.println("(" + p[0] + ", " + p[1] + ")");
        }
    }
}

注意，以上代码中的 `maze` 是一个二维迷宫数组，'#' 表示墙，' ' 表示空地。`start` 和 `end` 分别为起点和终点的坐标。函数返回最短路径。