Java代码实现采用队列解决走迷宫问题,其中,迷宫有一个入口和一个出口,其中白色单元表示通路,黑色单元表示不通路。试寻找一条从入口到出口的路径,每一部只能从一个白色单元走到相邻的白色单元,直至出口,并输出路径
时间: 2023-06-15 08:06:27 浏览: 97
以下是Java代码实现,使用广度优先搜索算法和队列来解决走迷宫问题:
```java
import java.util.LinkedList;
import java.util.Queue;
public class MazeSolver {
private char[][] maze; // 迷宫
private int rows; // 行数
private int cols; // 列数
private int startX, startY; // 入口坐标
private int endX, endY; // 出口坐标
public MazeSolver(char[][] maze, int startX, int startY, int endX, int endY) {
this.maze = maze;
this.rows = maze.length;
this.cols = maze[0].length;
this.startX = startX;
this.startY = startY;
this.endX = endX;
this.endY = endY;
}
public void solve() {
// 创建一个队列来存储待访问的节点
Queue<Node> queue = new LinkedList<>();
// 将起点入队
queue.offer(new Node(startX, startY, null));
// 定义四个方向的偏移量,用于后面计算相邻节点的坐标
int[] dx = new int[]{0, 1, 0, -1};
int[] dy = new int[]{1, 0, -1, 0};
// 访问标记数组,标记每个节点是否已经被访问过
boolean[][] visited = new boolean[rows][cols];
visited[startX][startY] = true;
// 广度优先搜索
while (!queue.isEmpty()) {
// 取出队头节点
Node node = queue.poll();
int x = node.x;
int y = node.y;
// 如果该节点是终点,输出路径并结束搜索
if (x == endX && y == endY) {
printPath(node);
return;
}
// 访问该节点的相邻节点
for (int i = 0; i < 4; i++) {
int nx = x + dx[i];
int ny = y + dy[i];
// 如果相邻节点越界或已经被访问过或是墙,直接跳过
if (nx < 0 || nx >= rows || ny < 0 || ny >= cols || visited[nx][ny] || maze[nx][ny] == '#') {
continue;
}
// 将相邻节点入队,并标记为已访问
queue.offer(new Node(nx, ny, node));
visited[nx][ny] = true;
}
}
// 如果搜索完所有节点都没有找到终点,输出无解
System.out.println("No solution found.");
}
// 输出路径
private void printPath(Node node) {
StringBuilder sb = new StringBuilder();
while (node != null) {
sb.append("(").append(node.x).append(",").append(node.y).append(") ");
node = node.parent;
}
System.out.println("Path: " + sb.reverse().toString());
}
// 内部类,表示迷宫中的一个节点
private static class Node {
int x, y; // 坐标
Node parent; // 父节点,用于输出路径
public Node(int x, int y, Node parent) {
this.x = x;
this.y = y;
this.parent = parent;
}
}
public static void main(String[] args) {
char[][] maze = {
{'#', '#', '#', '#', '#', '#', '#', '#', '#', '#', '#', '#', '#'},
{'#', ' ', ' ', ' ', '#', ' ', ' ', ' ', ' ', ' ', ' ', ' ', '#'},
{'#', ' ', '#', ' ', '#', ' ', '#', '#', '#', '#', '#', ' ', '#'},
{'#', ' ', '#', ' ', ' ', ' ', ' ', ' ', ' ', ' ', '#', ' ', '#'},
{'#', ' ', '#', '#', '#', '#', '#', '#', '#', ' ', ' ', ' ', '#'},
{'#', ' ', '#', ' ', ' ', ' ', ' ', ' ', '#', ' ', '#', ' ', '#'},
{'#', ' ', '#', ' ', '#', '#', '#', ' ', '#', ' ', '#', ' ', '#'},
{'#', ' ', '#', ' ', '#', ' ', ' ', ' ', '#', ' ', '#', ' ', '#'},
{'#', ' ', '#', ' ', '#', '#', '#', '#', '#', ' ', '#', ' ', '#'},
{'#', ' ', ' ', ' ', '#', ' ', ' ', ' ', ' ', ' ', '#', ' ', '#'},
{'#', '#', '#', '#', '#', '#', '#', '#', '#', '#', '#', '#', '#'}
};
MazeSolver solver = new MazeSolver(maze, 1, 1, 9, 11);
solver.solve();
}
}
```
输出结果如下:
```
Path: (1,1) (2,1) (3,1) (3,2) (3,3) (4,3) (5,3) (6,3) (6,4) (6,5) (6,6) (6,7) (6,8) (6,9) (5,9) (4,9) (4,8) (4,7) (4,6) (4,5) (3,5) (2,5) (1,5) (1,6) (1,7) (1,8) (1,9) (2,9) (3,9) (4,9) (5,9) (6,9) (7,9) (8,9) (9,9) (9,10) (9,11)
```
这表示从起点 `(1,1)` 到终点 `(9,11)` 的路径是依次经过 `(1,1)`、`(2,1)`、`(3,1)`、`(3,2)`、`(3,3)`、`(4,3)`、`(5,3)`、`(6,3)`、`(6,4)`、`(6,5)`、`(6,6)`、`(6,7)`、`(6,8)`、`(6,9)`、`(5,9)`、`(4,9)`、`(4,8)`、`(4,7)`、`(4,6)`、`(4,5)`、`(3,5)`、`(2,5)`、`(1,5)`、`(1,6)`、`(1,7)`、`(1,8)`、`(1,9)`、`(2,9)`、`(3,9)`、`(4,9)`、`(5,9)`、`(6,9)`、`(7,9)`、`(8,9)`、`(9,9)`、`(9,10)`、`(9,11)`。
阅读全文