再帰的メイズソルバメソッド

Question

0と1で満たされた2次元のchar配列が与えられ、0は壁を表し、1は有効なパスを表します。findPath（int r、int c）という再帰的メソッドを開発しました。 'x'でマークされた迷路で。このメソッドは、迷路の現在の行と列を取り込み、有効なパスを見つけて '+'でその有効なパスをマークするまで、N、E、S、Wの方向に進みます。壁によってすべての方向がブロックされていることがわかった場合、この方法では、これが当てはまるまでバックトラックし、そのパスに「F」を付けてマークして、悪いパスを象徴します。

今、findPathメソッドがすべての方向を横断するように見えない理由を理解できません。私の表示方法は、渡した座標から始まり、そこから移動しないプログラムを示しています。これは？ここで

は私のドライバクラス

public class MazeMain2 
{ 
    public static void main(String[]args) 
    { 

    char[][] mazeArr = {{'0','0','0','1','0','0','0','0','0','0','0','0','0','0','0'}, 
       {'0','0','0','1','0','0','0','0','1','0','0','0','0','1','0'}, 
       {'0','0','0','1','1','1','1','1','1','1','1','1','0','0','0'}, 
       {'0','0','0','1','0','0','0','0','0','0','0','1','0','0','0'}, 
       {'0','0','0','1','1','1','1','1','0','0','0','1','0','0','0'}, 
       {'0','0','0','0','0','0','0','1','0','0','0','1','0','0','0'}, 
       {'0','0','0','0','1','1','1','1','0','0','0','1','0','0','0'}, 
       {'0','0','0','0','1','0','0','1','0','0','0','1','0','1','0'}, 
       {'0','0','0','0','1','0','0','1','0','0','0','0','0','0','0'}, 
       {'0','0','0','0','1','0','0','0','0','0','0','0','0','0','0'}, 
       {'0','0','0','0','1','1','1','1','1','1','1','0','0','0','0'}, 
       {'0','0','0','0','0','0','0','0','0','0','1','0','0','0','0'}, 
       {'0','0','0','0','0','0','0','0','0','0','1','0','0','0','0'}, 
       {'0','0','0','0','0','1','0','0','0','0','1','1','1','1','0'}, 
       {'0','0','0','0','0','0','0','0','0','0','1','0','0','0','0'}}; 

    MazeSolver2 mazeS = new MazeSolver2(mazeArr); 

    mazeS.markEntry(); 
    mazeS.markExit(); 

    mazeS.solve(0, mazeS.start); 


    } 
} 

であり、ここでfindPath方法と私の迷路のソルバークラスです

public class MazeSolver2 
{ 
    int start; 
    int exit; 

    char[][] maze; 

public MazeSolver2(char[][] currentMaze) 
{ 
    maze = currentMaze; 
} 

//Finds where the first 1 is in the top row of the 
//maze (entrance) 
public void markEntry() 
{ 
    for(int x = 0; x < maze.length; x++) 
    { 
     if(maze[0][x] == '1') 
     { 
      maze[0][x] = 'E'; 
      start = x; 
     } 
    } 
} 

//Finds where the last 1 is in the bottom row of the 
//maze (exit) 
public void markExit() 
{ 
    for(int x = 0; x < maze.length; x++) 
    { 
     if(maze[maze.length - 1][x] == '1') 
     { 
      maze[maze.length - 1][x] = 'x'; 
      exit = x; 
     } 
    } 
} 

public void solve(int x, int y) 
{ 
    if(findPath(x, y)) 
    { 
     System.out.println(maze[x][y]); 
    } 
    else 
     System.out.println("No solution"); 

} 

public boolean findPath(int r, int c) 
{ 
    displayMaze(maze); 

    //Found the exit 
    if(maze[r][c] == 'x') 
    { 
     return true; 
    } 


    if(maze[r][c] == '0' || maze[r][c] == '+' || maze[r][c] == 'F') 
    { 
     return false; 
    } 

    maze[r][c] = '+'; 

    //If row is currently at zero then don't check north 
    //direction because it will be outside of the maze 
    if(r <= 0) 
    { 
     if(findPath(r, c++)) 
     { 
      return true; 
     } 


     if(findPath(r++, c)) 
     { 
      return true; 
     } 

     if(findPath(r, c--)) 
     { 
      return true; 
     } 

    } 

    else 
    { 
     //check N, E, S, W directions 
     if(findPath(r--, c) || findPath(r, c++) || 
      findPath(r++, c) || findPath(r, c--)) 
     { 
      return true; 
     } 
    } 

    //Marking the bad path 
    maze[r][c] = 'F'; 

    return false; 

} 

//Displays maze 
public void displayMaze(char[][] maze) 
{ 

     for(int row = 0; row < maze.length; row++) 
     { 
      for(int col = 0; col < maze.length; col++) 
      { 
       if(col == 14) 
       { 
        System.out.print(maze[row][col]); 
        System.out.println(); 
       } 
       else 
       { 
        System.out.print(maze[row][col]); 
       } 
      } 
     } 

    System.out.println(); 
    } 
} 

Answer 1

あなたのアルゴリズムでは、私は右感じていない自分自身にいくつかの流れを、持っています指摘する。迷路のトラバースの問題を検索し、多くの良いチュートリアルを得ることができます。

ただし、メソッド呼び出しには注意してください。 findPath(int r, int c)がfindPath(5, 5)で呼び出された場合、findPath(r, c++)への呼び出しでは、ではなく、findPath(5, 5)の値が再び渡されることに注意してください。

その場合findPath(r, c++)が現在値cで呼び出され、その後c++が実行されるためです。

同じことが事実を理解するのは良いアイデアは方法findPath()の起動時の値int r, int cを印刷することである

など、findPath(r, c--) findPath(r++ , c)などのために行きます。 ポストインクリメント/デクリメント（x ++/- x）とプリインクリメント/デクリメント（++ x/- x）で少し再生します。

希望します。