質問する

7*7グリッド迷路から脱出する経路の指数を出力するプログラムを作成します.
始点はメッシュの(1,1)座標,脱出終点は(7,7)座標である.仕切り板1は壁、0は通路です.
格子板の移動は上下左右のみ移動します.迷宮が
上の地図から始点から終点までの方法は8種類あります.

コード#コード#

public class Maze {
    static int[][] maze = new int[8][8];
    static int answer = 0;
    static int[][] direction = {{-1,0},{0,1},{1,0},{0,-1}};
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        for(int i=1; i<8; i++){
            for(int j=1; j<8; j++){
                maze[i][j] = sc.nextInt();
            }
        }

        dfs(1,1);

        System.out.println(answer);
    }
    public static void dfs(int x, int y){
        if(x>7 || y>7 || x<1 || y<1) return;
        if(maze[x][y] == 1) return;
        if(x==7 && y==7){
            answer++;
        }else{
            for(int[] dir : direction){
                maze[x][y] = 1;
                dfs(x+dir[0], y+dir[1]);
                maze[x][y] = 0;
            }
        }
    }
}

説明:

講師のコードは論理全体と変わらない.7*7メッシュサイズのラビリンスを作成するため、ラビリンスという2次元アレイを[8][8].これは,0 indexを用いず,1−7のみを用いたためである.これは単独では説明しないそれからdirectionを2次元配列に指定して、2つの1次元配列をx,yにして使うことができて、私のように早めに2次元配列を入れることができます.2 D配列の値の意味は,北,東,南,西の4つの方向から探索するためであり,dfsパラメータからそれらの座標値が急速に変化することが分かる.
dfs内の逆追跡条件を確認します.

メッシュの範囲を超えた場合、dfsは終了します.

座標系の値が1の場合、dfsは壁またはすでに通っている道に遭遇するため終了します.

上記のすべてのトレース条件を満たさない場合は、現在の座標値が7,7であることを確認します.7、7であれば出口に到達するので、答えの値を増やします.そうでなければ探索中なので、今踏んでいる座標は1で表され、戻ってこないようにdfsを実行した後、現在の座標を0に戻します.
以前迷宮探索DFS問題をやったことがあるので簡単にできます.しかし、以前は問題を解く時にまだ過程を理解していなかったので、コードに従って打っただけで、今回の問題を解く時に論理的な動作過程を理解して、問題を解く時も楽しかったです!