Java代码实现采用基本队列解决走迷宫问题,其中,迷宫有一个入口和一个出口,其中白色单元表示通路,黑色单元表示不通路。试寻找一条从入口到出口的路径,每一部只能从一个白色单元走到相邻的白色单元,直至出口,并输出路径
时间: 2023-06-17 20:03:12 浏览: 145
以下是基于队列实现走迷宫问题的Java代码:
```java
import java.util.*;
public class MazeSolver {
// 迷宫的行数和列数
private int rows;
private int cols;
// 迷宫中的起点和终点
private int startRow;
private int startCol;
private int endRow;
private int endCol;
// 迷宫中每个单元格的状态:0表示通路,1表示障碍
private int[][] maze;
// 记录每个单元格是否被访问过
private boolean[][] visited;
// 记录每个单元格的前驱单元格
private Point[][] predecessor;
public MazeSolver(int[][] maze, int startRow, int startCol, int endRow, int endCol) {
this.maze = maze;
this.rows = maze.length;
this.cols = maze[0].length;
this.startRow = startRow;
this.startCol = startCol;
this.endRow = endRow;
this.endCol = endCol;
this.visited = new boolean[rows][cols];
this.predecessor = new Point[rows][cols];
}
// 判断某个单元格是否可以访问
private boolean isValid(int row, int col) {
if (row < 0 || row >= rows || col < 0 || col >= cols) {
return false;
}
if (maze[row][col] == 1 || visited[row][col]) {
return false;
}
return true;
}
// 执行广度优先搜索
public void solve() {
Queue<Point> queue = new LinkedList<>();
Point start = new Point(startRow, startCol);
queue.offer(start);
visited[startRow][startCol] = true;
while (!queue.isEmpty()) {
Point cur = queue.poll();
if (cur.row == endRow && cur.col == endCol) {
return;
}
// 将当前单元格的相邻单元格加入队列
if (isValid(cur.row - 1, cur.col)) {
Point next = new Point(cur.row - 1, cur.col);
queue.offer(next);
visited[next.row][next.col] = true;
predecessor[next.row][next.col] = cur;
}
if (isValid(cur.row + 1, cur.col)) {
Point next = new Point(cur.row + 1, cur.col);
queue.offer(next);
visited[next.row][next.col] = true;
predecessor[next.row][next.col] = cur;
}
if (isValid(cur.row, cur.col - 1)) {
Point next = new Point(cur.row, cur.col - 1);
queue.offer(next);
visited[next.row][next.col] = true;
predecessor[next.row][next.col] = cur;
}
if (isValid(cur.row, cur.col + 1)) {
Point next = new Point(cur.row, cur.col + 1);
queue.offer(next);
visited[next.row][next.col] = true;
predecessor[next.row][next.col] = cur;
}
}
}
// 输出路径
public void printPath() {
Point cur = new Point(endRow, endCol);
Stack<Point> stack = new Stack<>();
while (cur != null) {
stack.push(cur);
cur = predecessor[cur.row][cur.col];
}
while (!stack.isEmpty()) {
Point p = stack.pop();
System.out.print("(" + p.row + "," + p.col + ")");
if (!stack.isEmpty()) {
System.out.print(" -> ");
}
}
}
// 测试
public static void main(String[] args) {
int[][] maze = {
{0, 1, 0, 0, 0},
{0, 1, 0, 1, 0},
{0, 0, 0, 0, 0},
{0, 1, 1, 1, 0},
{0, 0, 0, 1, 0}
};
MazeSolver solver = new MazeSolver(maze, 0, 0, 4, 4);
solver.solve();
solver.printPath();
}
}
// 单元格类
class Point {
public int row;
public int col;
public Point(int row, int col) {
this.row = row;
this.col = col;
}
}
```
以上代码中,我们使用了一个队列来存储待访问的单元格。具体的实现过程如下:
1. 将起点加入队列,并将其标记为已访问。
2. 每次从队列中取出队首元素(当前单元格),并判断它的相邻单元格是否可以访问。如果可以访问,就将相邻单元格加入队列,并标记为已访问,并记录它的前驱单元格。
3. 重复步骤2,直到队列为空或者找到了终点。
4. 如果找到了终点,就可以根据每个单元格的前驱单元格从终点往回推出一条路径。
阅读全文