迷宫问题数据结构最短路径java

迷宫问题可以使用图论中的最短路径算法来解决，其中比较常用的是广度优先搜索（BFS）或Dijkstra算法。我们可以通过在迷宫中搜索从起点到终点的所有可能路径，并寻找其中最短的路径。

具体实现中，可以将迷宫看作一个二维数组，通过BFS或Dijkstra算法搜索从起点（通常为左上角）到终点（通常为右下角）的最短路径。在搜索过程中，需要记录每个点的距离和是否已经被访问过。

以下是BFS算法的Java实现代码：

import java.util.*;

public class Maze {
    private static final int[][] directions = {{-1, 0}, {0, 1}, {1, 0}, {0, -1}}; // 上右下左四个方向
    private int[][] maze;
    private int rows;
    private int cols;

    public Maze(int[][] maze) {
        this.maze = maze;
        this.rows = maze.length;
        this.cols = maze[0].length;
    }

    public int shortestPath() {
        Queue<int[]> queue = new LinkedList<>(); // 存放当前正在遍历的节点
        boolean[][] visited = new boolean[rows][cols]; // 记录节点是否已经被遍历过
        queue.offer(new int[]{0, 0}); // 将起点放入队列
        visited[0][0] = true;

        int steps = 0; // 记录步数
        while (!queue.isEmpty()) {
            int size = queue.size();
            while (size-- > 0) {
                int[] curr = queue.poll(); // 取出队首节点
                if (curr[0] == rows - 1 && curr[1] == cols - 1) {
                    return steps; // 已经到达终点，返回最短路径长度
                }
                for (int[] dir : directions) {
                    int newRow = curr[0] + dir[0];                    int newCol = curr[1] + dir[1];
                    if (newRow >= 0 && newRow < rows && newCol >= 0 && newCol < cols
                            && maze[newRow][newCol] == 0 && !visited[newRow][newCol]) {
                        queue.offer(new int[]{newRow, newCol}); // 将新节点加入队列
                        visited[newRow][newCol] = true;
                    }
                }
            }
            steps++; // BFS遍历完一层，步数+1
        }

        return -1; // 无法到达终点，返回-1
    }
}

其中，输入的`maze`是一个二维数组，代表迷宫，0表示可通过的路径，1表示障碍物。`shortestPath`方法返回从起点到终点的最短路径长度，如果无法到达终点则返回-1。