どのように再帰を使用して迷路から出る？

Question

0 - 非訪問、1 - 障害物（ブロック位置）、2 - 訪問、-1 - 出力、（x、y） - 開始位置の行列で表される迷路を考えてみましょう。私は再帰を使って、最初から何らかの出力までのパスを見つけたいと思っています。

int[] x_dir = new int[] { 0, 0, -1, 1 }; // x, x, x-1, x + 1 
int[] y_dir = new int[] { -1, 1, 0, 0 }; // y-1, y+1, y, y 

bool dfs(int[,] maze, int x, int y, int[] x_dir, int[] y_dir) 
{ 
    if (maze[x, y] == -1) { return true; } // output cell marked -1 

    int i = 0; 
    while (i < 4 && !dfs(maze, x + x_dir[i], y + y_dir[i], x_dir, y_dir)) 
    { 
     ++i; 
    } 
    return (i > 4) ? false : true; 
} 

は、私は2つの問題を抱えている：私はエッジケース（IndexOutOfRangeException inside maze[x,y]）とどのようにパスを印刷することを処理する方法がわかりません。 お願いします。

Answer 1

パスを印刷するには、パスを記録する必要があります。これは、その目的のためのパラメータを追加することを示唆しています。間違った回しを入れないように気をつけなければなりません。少なくとも、あなたがそれが何であるかを知ったら、取り除くようにしなければなりません。

dfsへの呼び出しごとに実行したステップを印刷してtrueを返した場合は、パスは逆になります。

エッジ（コーナーではない）の場合：迷路内のそれらの位置にアクセスしようとする前に、x+x_dir[i]とy+y_dir[i]が迷路の有効な指標であることを確認する必要があります。

Answer 2

印刷パスの場合は、追加の行列を作成し、その中に情報を格納することができます。最長の部分配列問題と同様に、動的プログラミングで解決されます。

または いくつかの追加のマトリックスを作成するのではなく、同じマトリックスを使用することができます。パスを追跡するために、出力セルを見つけたら状態を保存してください。

while (i < 4) 
{ 
    if(!dfs(maze, x + x_dir[i], y + y_dir[i], x_dir, y_dir)) 
     ++i; 
    else 
     maze[x][y]=255; 
} 

その後、要素255 を細胞に従うが、この情報がお役に立てば幸いです。