Java代码实现采用不定义方向的队列解决走迷宫问题,其中,迷宫有一个入口和一个出口,其中白色单元表示通路,黑色单元表示不通路。试寻找一条从入口到出口的路径,每一部只能从一个白色单元走到相邻的白色单元,直至出口,并输出路径
时间: 2023-06-17 09:03:16 浏览: 97
以下是Java代码实现:
```java
import java.util.LinkedList;
import java.util.Queue;
public class MazeSolver {
private static final int[][] DIRECTIONS = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}}; // 定义四个方向的偏移量
public static void main(String[] args) {
int[][] maze = {
{0, 0, 0, 0, 0, 0, 0, 0, 0},
{0, 1, 1, 1, 0, 1, 1, 1, 0},
{0, 1, 0, 1, 0, 0, 0, 1, 0},
{0, 1, 0, 1, 1, 1, 0, 1, 0},
{0, 1, 0, 0, 0, 1, 0, 1, 0},
{0, 1, 1, 1, 0, 1, 0, 1, 0},
{0, 0, 0, 1, 0, 1, 0, 1, 0},
{0, 1, 1, 1, 0, 1, 1, 1, 0},
{0, 0, 0, 0, 0, 0, 0, 0, 0}
}; // 迷宫地图,0表示墙,1表示通路
int[] start = {1, 1}; // 入口
int[] end = {7, 7}; // 出口
int[][] path = solveMaze(maze, start, end); // 求解迷宫
if (path == null) {
System.out.println("迷宫无解!");
} else {
for (int i = 0; i < path.length; i++) {
System.out.println("(" + path[i][0] + ", " + path[i][1] + ")");
}
}
}
public static int[][] solveMaze(int[][] maze, int[] start, int[] end) {
int m = maze.length;
int n = maze[0].length;
boolean[][] visited = new boolean[m][n]; // 标记是否访问过
int[][] prev = new int[m][n]; // 存储每个节点的前一个节点
Queue<int[]> queue = new LinkedList<>(); // 定义队列
queue.offer(start); // 将起点加入队列
visited[start[0]][start[1]] = true; // 将起点标记为已访问
while (!queue.isEmpty()) {
int[] curr = queue.poll(); // 取出队首节点
if (curr[0] == end[0] && curr[1] == end[1]) { // 到达终点
break;
}
for (int[] direction : DIRECTIONS) { // 遍历四个方向
int nextX = curr[0] + direction[0];
int nextY = curr[1] + direction[1];
if (nextX >= 0 && nextX < m && nextY >= 0 && nextY < n && maze[nextX][nextY] == 1 && !visited[nextX][nextY]) { // 如果下一个节点是合法的
queue.offer(new int[]{nextX, nextY}); // 将下一个节点加入队列
visited[nextX][nextY] = true; // 标记下一个节点为已访问
prev[nextX][nextY] = curr; // 存储下一个节点的前一个节点
}
}
}
if (!visited[end[0]][end[1]]) { // 如果终点不可达
return null;
}
int[][] path = new int[m * n][2]; // 存储路径
int i = 0;
int[] curr = end;
while (curr[0] != start[0] || curr[1] != start[1]) { // 从终点开始回溯到起点
path[i++] = curr;
curr = prev[curr[0]][curr[1]];
}
path[i] = start; // 将起点加入路径
int[][] result = new int[i + 1][2]; // 创建正确大小的路径数组
for (int j = 0; j < result.length; j++) {
result[j] = path[i--]; // 将路径数组倒序存入结果数组
}
return result;
}
}
```
该算法采用广度优先搜索,使用队列存储待访问的节点。每次从队列中取出队首节点,遍历四个方向上的相邻节点,将合法的节点加入队列。使用一个二维数组 `prev` 存储每个节点的前一个节点,以便后续回溯构造路径。当遍历到终点时,即可结束搜索,回溯构造路径。
注意,本算法中假设起点和终点是合法的,并且起点不等于终点。如果需要考虑这些特殊情况,可以在代码中进行特判。
阅读全文