使用 BFS 打印最短路径

Question

我正在创建一个使用 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

Answer 1

我不确定我是否完全理解了这个问题，但是您的 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;
}

使用 BFS 打印最短路径

Printing the shortest path with BFS

java

algorithm

breadth-first-search

maze