BFS 如何在迷宫求解器中找到最小路径

Question

我卡在了一个问题的解决方案上。

问题=> 给你一个正方形网格，其中一些单元格是打开的 (.)，一些单元格是封闭的 (X)。您的棋子可以沿着任何行或列移动，直到它到达网格的边缘或被阻塞的单元格。给定一个网格、一个起点和一个目标，确定到达目标的最少步数。

Example =>
...
.X.
...

起始位置(0,0) 所以从左上角开始。目标是(1,2) 路径是(0,0)->(0,2)->(1,2)。需要采取行动才能达到目标。输出 = 2

解决方案=> BFS 使用队列。

但是BFS如何到达最小路径，例如如果起点和终点之间存在多条路径，那么BFS如何到达最小路径？

这是我针对上述问题的解决方案。但是没用。

class Pair{
int x,y;
Pair(int a,int b){x=a;y=b;}
}

class Result {  
public static int minimumMoves(List<String> grid, int startX, int startY, int goalX, int goalY) 
{
    int n=grid.get(0).length();

    ArrayDeque<Pair> q=new ArrayDeque<Pair>();
    Pair location[][]=new Pair[n][n];
    char color[][]=new char[n][n];
    
    //default color a mean it is neither in queue nor explore 
    //till now, b mean it is in queue, c means it already explore
    for(int i=0;i<n;i++){
        for(int j=0;j<n;j++){
            color[i][j]='a';
        }
    }
    
    q.addLast(new Pair(startX,startY));
    
    int tempx,tempy,tempi,tempj;
    
    
    while(!q.isEmpty()){
            tempx=q.peekFirst().x;
            tempy=q.peekFirst().y;
            q.removeFirst();
            color[tempx][tempy]='c';
            tempj=tempy-1;
            tempi=tempx;

            //cheking unvisited node around -X axis
            while(tempj>=0){
                if(color[tempi][tempj]!='a' || grid.get(tempi).charAt(tempj)!='.'){
                    break;
                }
                q.addLast(new Pair(tempi,tempj));
                color[tempi][tempj]='b';
                location[tempi][tempj]=new Pair(tempx,tempy);
                tempj--;
            }
            
            //checking unvisited node around +X axis
            tempi=tempx;
            tempj=tempy+1;
            while(tempj<n){
                if(color[tempi][tempj]!='a' || grid.get(tempi).charAt(tempj)!='.'){
                    break;
                }
                q.addLast(new Pair(tempi,tempj));
                color[tempi][tempj]='b';
                location[tempi][tempj]=new Pair(tempx,tempy);
                tempj++;
            }
            
            //checking unvisited node around +Y axis
            tempi=tempx-1;
            tempj=tempy;
            while(tempi>=0){
                if(color[tempi][tempj]!='a' || grid.get(tempi).charAt(tempj)!='.'){
                    break;
                }
                q.addLast(new Pair(tempi,tempj));
                color[tempi][tempj]='b';
                location[tempi][tempj]=new Pair(tempx,tempy);
                tempi--;
            }
            
            checking unvisited node around -Y axis
            tempi=tempx+1;
            tempj=tempy;
            while(tempi<n){
                if(color[tempi][tempj]!='a' || grid.get(tempi).charAt(tempj)!='.'){
                    break;
                }
                q.addLast(new Pair(tempi,tempj));
                color[tempi][tempj]='b';
                location[tempi][tempj]=new Pair(tempx,tempy);
                tempi++;
            }
    }//end of main while

    //for track the path
    Stack<Pair> stack=new Stack<Pair>();
    
    //If path doesn't exist
    if(location[goalX][goalY]==null){
        return -1;
    }

    boolean move=true;
    stack.push(new Pair(goalX,goalY));
    while(move){
        tempi=stack.peek().x;
        tempj=stack.peek().y;
        stack.push(location[tempi][tempj]);
        if(tempi==startX && tempj==startY){
            move=false;
        }
    }
    System.out.println(stack);
    return stack.size()-2;
}

}

这里我的算法只找到路径。不是最小路径。谁能告诉我 BFS 如何在这里找到最小路径以及我应该在我的代码中更改什么？

Answer 1

BFS 通过同心向外移动找到最小路径，因此第 1 轮中的所有内容都离起点 1 远，所有添加到那里的方块都离起点 2 远，依此类推。这意味着使用 BFS 查找路径的基本思想是好的，不幸的是实现起来有点困难和缓慢。

另一种查看方式是将网格视为图形，所有方块都与所有其他方块上下左右相连，直到它们碰到边缘或障碍物。

第三种思考方式就像洪水填充，第一轮只填充开始，下一轮填充所有可以从中访问的内容，依此类推。

最重要的是，当你看到 b.

时，你会崩溃

aabbaaaaaa
aabbbaaaaa
babbbaaaaa
babbbaaaaa
babbbaaaaa
babbbaaaaa
bbbbbaaaaa
bbbbbaaaaa
bCbbbAAAAA
cccccaaaaa

处理大写字母C时停止，因为它被b和c包围。因此你不检查 As.

我对代码进行了一些修改，请注意我不是 java 程序员......我在尝试解决它时遇到的主要问题是超时。我相信这可以在没有位置数组的情况下通过记录我们有多少代 BFS 来解决运行，这应该会节省大量内存和时间。

class Pair{
    int x,y;
    Pair(int a,int b){x=a;y=b;}
    public String toString() {
        return "[" + x + "," + y + "]";
    }
}

class Result {

    /*
     * Complete the 'minimumMoves' function below.
     *
     * The function is expected to return an INTEGER.
     * The function accepts following parameters:
     *  1. STRING_ARRAY grid
     *  2. INTEGER startX
     *  3. INTEGER startY
     *  4. INTEGER goalX
     *  5. INTEGER goalY
     */
 
    public static int minimumMoves(List<String> grid, int startX, int startY, int goalX, int goalY) {
    
    if (startX==goalX&&startY==goalY)
        return 0;
        
    startX += 1;
    startY += 1;
    goalX += 1;
    goalY += 1;
        
    int n=grid.get(0).length();

    Pair dirs[] = {new Pair(-1,0), new Pair(+1,0), new Pair(0,-1), new Pair(0,+1)};

    ArrayDeque<Pair> q=new ArrayDeque<Pair>();
    Pair location[][]=new Pair[n+2][n+2];
    char color[][]=new char[n+2][n+2];
    
    //default color a mean it is neither in queue nor explore 
    //till now, b mean it is in queue, c means it already explore
    for(int i=0;i<n+2;i++){
        for(int j=0;j<n+2;j++){
            if (i == 0 || i == n+1 ||j == 0 || j == n+1 || // boarder
                grid.get(i-1).charAt(j-1)!='.')
                color[i][j]='x';
            else
                color[i][j]='a';
        }
    }
    
    q.addLast(new Pair(startX,startY));
    
    int tempx,tempy,tempi,tempj;
    
    
    while(!q.isEmpty()){
        tempx=q.peekFirst().x;
        tempy=q.peekFirst().y;
        q.removeFirst();
        if(location[goalX][goalY]!=null){
            System.out.println("Goal reached");
            break;
        }
        color[tempx][tempy]='c';
        
        for (Pair dir : dirs ) {
            tempi=tempx;
            tempj=tempy;

            while(true){
                tempi+=dir.x;
                tempj+=dir.y;

                if (color[tempi][tempj]=='x') { // includes boarder
                    break;
                }
                if (color[tempi][tempj]>='b') {
                    continue;
                }
                q.addLast(new Pair(tempi,tempj));
                color[tempi][tempj]='b';
                location[tempi][tempj]=new Pair(tempx,tempy);                
            }
        }            

        // System.out.println(location[goalX][goalY]);
        // for(int i = 1; i < n+1; i++) {
        //     for(int j = 1; j < n+1; j++) {
        //         System.out.printf("%c", color[i][j]);
        //     }
        //     System.out.println();
        // }

    }//end of main while

    //for track the path
    Stack<Pair> stack=new Stack<Pair>();
    
    //If path doesn't exist
    if(location[goalX][goalY]==null){
        System.out.printf("Gaol not reached %d %d", goalX, goalY);
        System.out.println();
        for(int i = 1; i < n+1; i++) {
            for(int j = 1; j < n+1; j++) {
                System.out.printf("%s", location[i][j]);
            }
            System.out.println();
        }

        return -1;
    }

    boolean move=true;
    int moves = 0;
    tempi = goalX;
    tempj = goalY;
    while(move){
        System.out.println(String.valueOf(tempi)+" "+ String.valueOf(tempj));
        moves = moves +1;
        Pair cur = location[tempi][tempj];
        tempi=cur.x;
        tempj=cur.y;
        if(tempi==startX && tempj==startY){
            move=false;
        }
    }
    System.out.println(moves);
    return moves;
   }

}

BFS 如何在迷宫求解器中找到最小路径

How BFS find the minimum path in maze solver

algorithm

breadth-first-search

data-structures