java - 再帰を使用するアルゴリズムで右の壁に固執して迷路を解くにはどうすればよいですか?

Question

次の 2 次元配列では、# は迷路の壁を表し、ドットは迷路を通る可能性のある経路の正方形を表します。移動は、ドットを含む配列内の場所に対してのみ行うことができます...迷路を「歩く」には、再帰的なメソッド 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");
}

}

score 0 · Accepted Answer

再帰が必要なため、おそらく 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

プログラムのエッジは、現在調べているセルの (最大で) 4 つの隣接セルです。出口を見つけたら、セルに印を付けて、元に戻ります。これが一般的な考え方です。詳細はご自身でご確認ください。

SOS (テーブルの境界に注意してください) お役に立てば幸いです

score 0 · Accepted Answer

次のアルゴリズムを使用しました。まだ出口にいない場合は、右に行こうとし、次に前進しようとし、次に左に行こうとします。これらのいずれかが末尾へのパスを返す場合、それが返されます。それらが 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 を返しました

java - 再帰を使用するアルゴリズムで右の壁に固執して迷路を解くにはどうすればよいですか?

2 に答える 2

Related

Reference