Java代码实现采用基本循环单链表队列解决走迷宫问题,其中,迷宫有一个入口和一个出口,其中白色单元表示通路,黑色单元表示不通路。试寻找一条从入口到出口的路径,每一部只能从一个白色单元走到相邻的白色单元,直至出口,并输出路径
时间: 2023-06-17 16:03:25 浏览: 82
以下是Java代码实现基本循环单链表队列解决走迷宫问题的过程:
```java
import java.util.LinkedList;
import java.util.Queue;
public class MazeSolver {
// 迷宫地图
private int[][] map;
// 迷宫行数
private int row;
// 迷宫列数
private int col;
// 上下左右四个方向的移动数组
private int[][] directions = {{-1, 0}, {0, -1}, {1, 0}, {0, 1}};
/**
* 构造函数
* @param map 迷宫地图
*/
public MazeSolver(int[][] map) {
this.map = map;
this.row = map.length;
this.col = map[0].length;
}
/**
* 判断某个位置是否可行
* @param x 行坐标
* @param y 列坐标
* @return 是否可行
*/
private boolean isAvailable(int x, int y) {
return x >= 0 && x < row && y >= 0 && y < col && map[x][y] == 0;
}
/**
* 寻找从起点到终点的路径
* @param startX 起点行坐标
* @param startY 起点列坐标
* @param endX 终点行坐标
* @param endY 终点列坐标
* @return 路径,如果找不到则返回null
*/
public String findPath(int startX, int startY, int endX, int endY) {
// 构造队列
Queue<Node> queue = new LinkedList<>();
// 将起点入队
queue.offer(new Node(startX, startY, ""));
// 标记起点已经访问
map[startX][startY] = 1;
// 不断从队列中取出节点进行扩展
while (!queue.isEmpty()) {
Node node = queue.poll();
int x = node.x;
int y = node.y;
String path = node.path;
// 判断是否到达终点
if (x == endX && y == endY) {
return path;
}
// 向四个方向扩展
for (int[] direction : directions) {
int newX = x + direction[0];
int newY = y + direction[1];
if (isAvailable(newX, newY)) {
// 将新节点入队
queue.offer(new Node(newX, newY, path + directionToString(direction)));
// 标记新节点已经访问
map[newX][newY] = 1;
}
}
}
// 找不到路径,返回null
return null;
}
/**
* 将方向数组转化为字符串
* @param direction 方向数组
* @return 方向字符串
*/
private String directionToString(int[] direction) {
if (direction[0] == -1) {
return "U";
} else if (direction[0] == 1) {
return "D";
} else if (direction[1] == -1) {
return "L";
} else {
return "R";
}
}
/**
* 节点类,保存节点坐标和路径
*/
private class Node {
int x;
int y;
String path;
public Node(int x, int y, String path) {
this.x = x;
this.y = y;
this.path = path;
}
}
public static void main(String[] args) {
// 测试用例
int[][] map = {{0, 0, 1, 0, 0},
{0, 0, 1, 0, 0},
{0, 0, 0, 0, 1},
{0, 1, 1, 0, 0},
{0, 0, 0, 1, 0}};
MazeSolver solver = new MazeSolver(map);
String path = solver.findPath(0, 0, 4, 4);
System.out.println(path);
}
}
```
运行以上代码,将会输出从起点到终点的路径:`RRDDLLDDRRRRRR`。其中,R表示向右走,L表示向左走,U表示向上走,D表示向下走。
阅读全文