java队列实现迷宫寻路
时间: 2023-09-18 20:14:41 浏览: 55
以下是使用 Java 队列实现迷宫寻路的示例代码:
```java
import java.util.LinkedList;
import java.util.Queue;
public class MazeSolver {
private int[][] maze;
private int[] start;
private int[] end;
private Queue<int[]> queue;
public MazeSolver(int[][] maze, int[] start, int[] end) {
this.maze = maze;
this.start = start;
this.end = end;
this.queue = new LinkedList<>();
this.queue.offer(start);
}
public int[][] solve() {
while (!queue.isEmpty()) {
int[] current = queue.poll();
int x = current[0];
int y = current[1];
if (x == end[0] && y == end[1]) {
return maze;
}
// 上下左右四个方向
int[][] directions = {{0, -1}, {0, 1}, {-1, 0}, {1, 0}};
for (int[] dir : directions) {
int nextX = x + dir[0];
int nextY = y + dir[1];
// 判断是否越界、是否是障碍物、是否已经走过
if (nextX >= 0 && nextX < maze.length && nextY >= 0 && nextY < maze[0].length
&& maze[nextX][nextY] == 0) {
maze[nextX][nextY] = maze[x][y] + 1;
queue.offer(new int[]{nextX, nextY});
}
}
}
return null; // 无解情况
}
}
```
在上述代码中,我们使用了一个二维数组 `maze` 来表示迷宫,其中 `0` 表示可走的路,`1` 表示障碍物。`start` 和 `end` 分别表示起点和终点的坐标。
我们使用一个队列 `queue` 来存储待访问的节点,初始时将起点加入队列中。然后在每次取出队列中的节点进行访问时,我们遍历其上下左右四个方向,并判断下一个节点是否满足可访问的条件(不越界、不是障碍物、未走过),如果满足条件,则将其加入队列,并将其值更新为当前节点的值加一。
最终,如果队列为空,说明无解;否则,返回更新后的 `maze` 数组即可。