迷宫问题如何选择方向求出最短路径java

解决迷宫问题的最短路径，可以使用广度优先搜索算法，具体实现方法如下：

1. 定义一个二维数组来表示迷宫地图，用 0 表示可以通过的路，用 1 表示障碍物或墙壁。

2. 定义一个队列来存储待访问的节点。

3. 定义一个二维数组来存储每个节点到起点的步数，初始化为无穷大。

4. 初始化起点的步数为 0，并将起点加入队列中。

5. 对于队列中的每个节点，依次遍历其周围的四个节点，如果该节点可以通过且未被访问过，则将其加入队列中，并将步数加 1。

6. 重复执行步骤 5，直到队列为空或者找到终点。

7. 如果找到终点，则按照从终点到起点的顺序，依次输出每个节点的坐标即可。

以下是具体的 Java 代码实现：

import java.util.*;

public class Maze {
    private static final int INF = Integer.MAX_VALUE;
    private static final int[][] dirs = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}};

    public static void main(String[] args) {
        int[][] maze = {{0, 0, 1, 0, 0},
                        {0, 0, 0, 0, 0},
                        {0, 0, 1, 0, 0},
                        {0, 1, 0, 0, 1},
                        {0, 0, 0, 0, 0}};

        int[] start = {0, 0}, end = {4, 4};
        int[][] dist = new int[maze.length][maze[0].length];
        for (int i = 0; i < maze.length; i++) {
            Arrays.fill(dist[i], INF);
        }

        Queue<int[]> queue = new LinkedList<>();
        queue.offer(start);
        dist[start[0]][start[1]] = 0;

        while (!queue.isEmpty()) {
            int[] curr = queue.poll();
            if (curr[0] == end[0] && curr[1] == end[1]) {
                break;
            }

            for (int[] dir : dirs) {
                int x = curr[0] + dir[0], y = curr[1] + dir[1];
                if (x >= 0 && x < maze.length && y >= 0 && y < maze[0].length && maze[x][y] == 0 && dist[x][y] == INF) {
                    queue.offer(new int[]{x, y});
                    dist[x][y] = dist[curr[0]][curr[1]] + 1;
                }
            }
        }

        List<int[]> path = new ArrayList<>();
        if (dist[end[0]][end[1]] != INF) {
            int[] curr = end;
            while (!Arrays.equals(curr, start)) {
                path.add(curr);
                for (int[] dir : dirs) {
                    int x = curr[0] + dir[0], y = curr[1] + dir[1];
                    if (x >= 0 && x < maze.length && y >= 0 && y < maze[0].length && maze[x][y] == 0 && dist[x][y] == dist[curr[0]][curr[1]] - 1) {
                        curr = new int[]{x, y};
                        break;
                    }
                }
            }
            path.add(start);
            Collections.reverse(path);
        }

        System.out.println(path);
    }
}

在示例代码中，我们先定义了一个迷宫地图 maze，起点 start 和终点 end，然后定义了一个 dist 数组来存储每个节点到起点的步数，初始化为无穷大。接着，我们使用广度优先搜索算法，依次遍历每个节点的周围四个节点，如果该节点可以通过且未被访问过，则将其加入队列中，并将步数加 1。最后，如果找到终点，则按照从终点到起点的顺序，依次输出每个节点的坐标即可。