java - 如何通过在使用递归的算法中坚持正确的墙壁来解决迷宫？

Question

在前面的二维数组中，# 代表迷宫的墙壁，圆点代表穿过迷宫的可能路径中的正方形。只能移动到数组中包含点的位置......我需要一个递归方法 mazeTraverse 来“行走”迷宫。它应该接收数组和迷宫的起始位置作为参数。当它试图定位迷宫的出口时，它应该在路径的每个方格中放置字符“X”。该方法应在每次移动后显示迷宫，以便用户可以观看迷宫已解决。

我不确定如何超越这一点。感谢任何可以提供帮助的人。

public class BonusMaze {
    public static void main(String args[]){
        char field[][]={
            {'#','#','#','#','#','#','#','#','#','#','#','#'},
            {'#','•','•','•','#','•','•','•','•','•','•','#',},
            {'•','•','#','•','#','•','#','#','#','#','•','#',},
            {'#','#','#','•','#','•','•','•','•','#','•','#',},
            {'#','•','•','•','•','#','#','#','•','#','•','•',},
            {'#','#','#','#','•','#','•','#','•','#','•','#',},
            {'#','•','•','#','•','#','•','#','•','#','•','#',},
            {'#','#','•','#','•','#','•','#','•','#','•','#',},
            {'#','•','•','•','•','•','•','•','•','#','•','#',},
            {'#','#','#','#','#','#','•','#','#','#','•','#',},
            {'#','•','•','•','•','•','•','#','•','•','•','#',},
            {'#','#','#','#','#','#','#','#','#','#','#','#'},
        };
        printField(field);

        mazeTraverse(field,2,0);

    }
    public static void mazeTraverse(char[][] field, int x, int y){
        field[2][0]='X';
        if(field[x+1][y]=='•'){
            field[x+1][y]='X';
            printField(field);
            mazeTraverse(field,x+1,y);
        }
        else if(field[x-1][y]=='•'){
            field[x-1][y]='X';
            printField(field);
            mazeTraverse(field,x+1,y);
        }
        else if(field[x][y+1]=='•'){
            field[x][y+1]='X';
            printField(field);
            mazeTraverse(field,x+1,y);
        }
        else if(field[x][y-1]=='•'){
            field[x][y-1]='X';
            printField(field);
            mazeTraverse(field,x+1,y);
        }
    }
    public static void printField(char[][] field){
        for(int x=0; x<11; x++){
            for(int y=0; y<11; y++){
                System.out.print(field[x][y]);
            }
            System.out.println();
        }
        System.out.print("\n\n");
    }
}

我已经把它改成了这个，但这一切都很古怪：

public class BonusMaze {
public static boolean east=true, north=false, south=false, west=false;
/*
 east=false; 
 north=false; 
 south=false;
 west=false;
 */
public static void main(String args[]){
    char field[][]={
        {'#','#','#','#','#','#','#','#','#','#','#','#'},
        {'#','•','•','•','#','•','•','•','•','•','•','#',},
        {'•','•','#','•','#','•','#','#','#','#','•','#',},
        {'#','#','#','•','#','•','•','•','•','#','•','#',},
        {'#','•','•','•','•','#','#','#','•','#','•','•',},
        {'#','#','#','#','•','#','•','#','•','#','•','#',},
        {'#','•','•','#','•','#','•','#','•','#','•','#',},
        {'#','#','•','#','•','#','•','#','•','#','•','#',},
        {'#','•','•','•','•','•','•','•','•','#','•','#',},
        {'#','#','#','#','#','#','•','#','#','#','•','#',},
        {'#','•','•','•','•','•','•','#','•','•','•','#',},
        {'#','#','#','#','#','#','#','#','#','#','#','#'},
    };
    printField(field);
    field[2][0]='X';
    mazeTraverse(field,2,0);

}
public static void mazeTraverse(char[][] field, int x, int y){
    if(x==2&&y==0){
        field[2][1]='X';
        mazeTraverse(field,2,1);
        printField(field);
    }
    if(east){
        if(field[x][y+1]=='•' || field[x+1][y]=='X'){
            field[x][y+1]='X';
        }
        if(field[x+1][y+1]=='•'){
            east=false; 
            north=false; 
            south=false;
            west=false;
            south=true;
            printField(field);
            mazeTraverse(field,x+1,y);
        }
        else if(field[x][y+2]=='•'){
            east=false; 
            north=false; 
            south=false;
            west=false;
            east=true;
            printField(field);
            mazeTraverse(field,x+1,y);
        }
        else if(field[x-1][y+1]=='•'){
            east=false; 
            north=false; 
            south=false;
            west=false;
            north=true;
            printField(field);
            mazeTraverse(field,x+1,y);
        }
        else if(field[x][y+1]=='#'){
            east=false; 
            north=false; 
            south=false;
            west=false;
            west=true;
            printField(field);
            mazeTraverse(field,x-1,y);
        }
    }
    else if(west){
        if(field[x-1][y]=='•' || field[x-1][y]=='X'){
            field[x-1][y]='X';
        }
        if(field[x+1][y+1]=='•'){
            east=false; 
            north=false; 
            south=false;
            west=false;
            south=true;
            printField(field);
            mazeTraverse(field,x+1,y);
        }
        else if(field[x][y+2]=='•'){
            east=false; 
            north=false; 
            south=false;
            west=false;
            east=true;
            printField(field);
            mazeTraverse(field,x+1,y);
        }
        else if(field[x-1][y+1]=='•'){
            east=false; 
            north=false; 
            south=false;
            west=false;
            north=true;
            printField(field);
            mazeTraverse(field,x+1,y);
        }
        else if(field[x][y+1]=='#'){
            east=false; 
            north=false; 
            south=false;
            west=false;
            west=true;
            printField(field);
            mazeTraverse(field,x-1,y);
        }
    }
    else if(north){
        if(field[x][y+1]=='•' || field[x][y+1]=='X'){
            field[x][y+1]='X';
        }
        if(field[x+1][y+1]=='•'){
            east=false; 
            north=false; 
            south=false;
            west=false;
            south=true;
            printField(field);
            mazeTraverse(field,x+1,y);
        }
        else if(field[x][y+2]=='•'){
            east=false; 
            north=false; 
            south=false;
            west=false;
            east=true;
            printField(field);
            mazeTraverse(field,x+1,y);
        }
        else if(field[x-1][y+1]=='•'){
            east=false; 
            north=false; 
            south=false;
            west=false;
            north=true;
            printField(field);
            mazeTraverse(field,x+1,y);
        }
        else if(field[x][y+1]=='#'){
            east=false; 
            north=false; 
            south=false;
            west=false;
            west=true;
            printField(field);
            mazeTraverse(field,x-1,y);
        }
    }
    else if(south){
        if(field[x][y-1]=='•' || field[x][y-1]=='X'){
            field[x][y-1]='X';
        }
        if(field[x+1][y+1]=='•'){
            east=false; 
            north=false; 
            south=false;
            west=false;
            south=true;
            printField(field);
            mazeTraverse(field,x+1,y);
        }
        else if(field[x][y+2]=='•'){
            east=false; 
            north=false; 
            south=false;
            west=false;
            east=true;
            printField(field);
            mazeTraverse(field,x+1,y);
        }
        else if(field[x-1][y+1]=='•'){
            east=false; 
            north=false; 
            south=false;
            west=false;
            north=true;
            printField(field);
            mazeTraverse(field,x+1,y);
        }
        else if(field[x][y+1]=='#'){
            east=false; 
            north=false; 
            south=false;
            west=false;
            west=true;
            printField(field);
            mazeTraverse(field,x-1,y);
        }
    }


    /*if(field[x+1][y]=='•'){
        field[x+1][y]='X';
        printField(field);
        mazeTraverse(field,x+1,y);
    }
    else if(field[x-1][y]=='•'){
        field[x-1][y]='X';
        printField(field);
        mazeTraverse(field,x+1,y);
    }
    else if(field[x][y+1]=='•'){
        field[x][y+1]='X';
        printField(field);
        mazeTraverse(field,x+1,y);
    }
    else if(field[x][y-1]=='•'){
        field[x][y-1]='X';
        printField(field);
        mazeTraverse(field,x+1,y);
    }*/
}
public static void printField(char[][] field){
    for(int x=0; x<12; x++){
        for(int y=0; y<12; y++){
            System.out.print(field[x][y]);
        }
        System.out.println();
    }
    System.out.print("\n\n");
}

}

Answer 1

当您需要递归时，您可能需要 DFS（深度优先搜索）。来自维基百科

 procedure DFS(G,v):
2      label v as discovered
3      for all edges e in G.adjacentEdges(v) do
4          if edge e is unexplored then
5              w ← G.adjacentVertex(v,e)
6              if vertex w is unexplored then
7                  label e as a discovered edge
8                  recursively call DFS(G,w)
9              else
10                 label e as a back edge
11      label v as explored

您的程序的边缘是您现在正在检查的单元格的四个（最多）邻居。如果你找到出口，你就是在标记单元格，然后返回。这是一般的想法。您现在可以自己了解详细信息。

SOS（注意你桌子的边缘）我希望我能帮到你

Answer 2

我使用了以下算法。如果还没有在出口处，它会尝试向右走，然后尝试向前走，然后尝试向左走。如果其中任何一个返回到末尾的路径，则返回该路径。如果它们返回 null，则尝试下一个方向。

通过始终尝试先正确，它正在模拟坚持正确的策略

traverse(Position p, Direction d, String pathSoFar)
   if atEndPosition(p)
     return pathSoFar + p;

   if canTravelRight(p, d)
      result = traverse(poitionToRight, directionToRight, pathSoFar + p)
      if result return result
   if canTravelForward(p, d)
      result = traverse(positionForward, d, pathSoFar + p)
      if result return result
   if canTravelLeft(p, d)
      result = traverse(positionToLeft, directionToLeft, pathSoFar + p)
   return result

我使用了一个非常简单的逻辑来找到向右的下一个方向，如果当前是北，那么下一个是东等等。如果向东移动，移动的逻辑同样简单，新的 x 位置是 oldx + 1，新的 y 位置是旧的y位置。在计算位置时我没有做任何边界检查，而是试图查看新位置是否在路径上。如果新位置是墙或 ArrayIndexOutOfBoundsException 则 canTravelxxx 返回 false