Java迷宫寻宝最短路径代码
时间: 2023-07-02 11:14:44 浏览: 122
java实现的求迷宫最短路径算法
4星 · 用户满意度95%
以下是一个简单的迷宫寻宝最短路径代码示例,使用广度优先搜索算法和队列:
```java
import java.util.LinkedList;
import java.util.Queue;
public class Maze {
// 定义迷宫,0 表示通路,1 表示障碍物
private 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}
};
// 定义开始和结束坐标
private int[] start = {0, 0};
private int[] end = {4, 4};
// 定义搜索函数
public int bfs() {
Queue<int[]> queue = new LinkedList<>(); // 用队列来实现广度优先搜索
queue.offer(start);
int[][] dirs = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}}; // 定义四个方向
int steps = 0;
while (!queue.isEmpty()) {
int size = queue.size();
for (int i = 0; i < size; i++) {
int[] curr = queue.poll();
if (curr[0] == end[0] && curr[1] == end[1]) {
return steps;
}
for (int[] dir : dirs) {
int x = curr[0] + dir[0];
int y = curr[1] + dir[1];
if (x >= 0 && x < maze.length && y >= 0 && y < maze[0].length && maze[x][y] == 0) {
maze[x][y] = 1; // 标记为已经访问过
queue.offer(new int[]{x, y});
}
}
}
steps++; // 记录步数
}
return -1; // 没有找到终点
}
// 测试函数
public static void main(String[] args) {
Maze maze = new Maze();
int steps = maze.bfs();
if (steps != -1) {
System.out.println("找到宝藏,最短路径为 " + steps + " 步!");
} else {
System.out.println("没有找到宝藏...");
}
}
}
```
运行结果:
```
找到宝藏,最短路径为 8 步!
```
这个示例代码使用了广度优先搜索算法,在搜索过程中使用一个队列来实现。首先将起点加入队列中,然后每次从队列中取出一个节点,判断是否是终点,如果是,则搜索结束,返回步数;否则,将该节点的邻居节点加入队列中继续搜索,同时将该节点标记为已经访问过。搜索结束后,如果能够找到终点,则返回最短路径的步数,否则返回 -1。
阅读全文