java - 使用 BFS 打印最短路径
问题描述
我正在创建一个使用Breadth First Search
算法的迷宫求解器,我想知道我是否可以以某种方式在网格上打印路径,而不是仅仅打印它经过的距离值以找到出口。这是下面的代码,提前致谢。
public List<Coords> solve(int x, int y) {
Queue<Coords> q = new LinkedList<>();
List<Coords> visited = new ArrayList<>();
Coords start = new Coords(x,y);
q.add(start);
visited.add(start);
while(!q.isEmpty()) {
Coords get = q.poll();
if(maze[get.x][get.y] == 3) {
System.out.println("found an exit!");
System.out.println("Distance: " + get.dist);
break;
}
if(!visited.contains(get)) {
visited.add(get);
}
if(isValid(get.x-1, get.y)) {
q.add(new Coords(get.x-1, get.y, get.dist+1));
}
if(isValid(get.x, get.y-1)) {
q.add(new Coords(get.x, get.y-1, get.dist+1));
}
if(isValid(get.x+1, get.y)) {
q.add(new Coords(get.x+1, get.y, get.dist+1));
}
if(isValid(get.x, get.y+1)) {
q.add(new Coords(get.x, get.y+1, get.dist+1));
}
}
return visited;
}
}
输出是:
found an exit! Distance: 20
解决方案
我不确定我是否完全理解这个问题,但是您的Queue<Coords> q
对象中是否已经有了这些数据?
如果是这样的话,那么你可以有这样的事情:
if (maze[get.x][get.y] == 3) {
System.out.println("found an exit!");
System.out.println("Distance: " + get.dist);
for(Coords c : q) {
System.out.println(c);
}
break;
}
推荐阅读
- c# - 使用 SSH.NET 和 WPF MVVM 进行并行文件上传的进度条
- excel - VBScript 将 .txt 文件导入 .xlsx 文件
- javascript - 如何将变量传递给onclick函数
- ios - 使用 JVFloatLabeledTextField 时 FloatingLabel Text Filed 占位符动画问题
- vue.js - Vue按英文字符串数字降序排序对象键值
- django - 创建 ModelForm 时 ImageField 不起作用
- python - 我无法从 matplotlib 导入 pyplot
- javascript - 为什么我在用 JS 编辑一些值后提交表单时得到空值?
- sql - 超出允许坐标区
- reactjs - React Dropzone 无法接受某些文件类型