再帰迷路にスタック

Question

クラス割り当てのために正しい方向にプッシュが必要です。私は旅行したパスを格納する変数/メソッドを作成することを述べた他の投稿を読んだが、それについて取得する方法がわからない... 編集済み9/28/16 は迷路の終点に到達できたまだ道を辿って印刷する方法はありません。 私は本当に、私は任意のポインタが大幅に高く評価され、移動した経路を追跡する方法を実装するかどうかはわかりません====

import java.io.*; 
import java.util.*; 

public class Maze 
{ 
    private static int rows, cols, startRow, startCol, nextRow, nextCol; 
    private static int endRow = 3; 
    private static int endCol = 34; 
    private static char[][] mazeBoard; 
    //private static char start = 'S'; 
    private static char end = 'E'; 
    //private boolean finish = false; 
    private char[][] explored = new char[rows][cols]; 

    //construct the maze board 
    public Maze() throws FileNotFoundException 
    { 
     Scanner in = new Scanner(new File("maze.txt")); 
     rows = in.nextInt(); 
     cols = in.nextInt(); 
     startRow = in.nextInt(); 
     startCol = in.nextInt(); 

     //fill out the mazeBoard 
     mazeBoard = new char[rows][cols]; 
     int i = 0; 
     while (in.hasNextLine()) 
     { 
      String inLine = in.nextLine(); 
      if (inLine.isEmpty()) 
      { 
      continue; 
      } 
      for (int j = 0;j < cols; j++) 
      { 
      char nextChar = inLine.charAt(j); 
      mazeBoard[i][j] = nextChar; 
      System.out.print(nextChar);  
      } 
      System.out.println(); 
      i++;   
     } 
     in.close(); 
    } 
    //updated the move method from void to boolean 
    public boolean move(int row, int col, int prevRow, int prevCol) 
{ 
    boolean finish = false; 
    prevRow = row; 
    prevCol = col; 
    //show location 
    System.out.println("row: " + row + " col: " + col); 

    //base case1 to check for out of bounds and not the previous position 
    if (row < 0 || col < 0 || row >= rows || col >= cols || row != prevRow || col != prevCol) 
     { return false; } 
    //base case2 to see if reached exit/end point 
    if (row == endRow && col == endCol) 
    { 
     System.out.println("Found the exit!"); 
     return true; 
    } 
    //base case3 to check for wall 
    if (mazeBoard[row][col] == '+' || mazeBoard[row][col] == '*') 
     { return false; } 
    mazeBoard[row][col] = '*'; 
     //try to move down 
     if (move(row + 1, col, prevRow, prevCol)) 
      { return true; } 
     //try to move right 
     if (move(row, col + 1, prevRow, prevCol)) 
      { return true; } 
     //try to move up 
     if (move(row - 1, col, prevRow, prevCol)) 
      { return true; } 
     //try to move left 
     if (move(row, col - 1, prevRow, prevCol)) 
      { return true; } 
      row = prevRow; 
      col = prevCol; 
    return false; 
} 

    public static void main(String[] args) throws FileNotFoundException 
    { 
     Maze maze = new Maze(); 
     maze.move(startRow, startCol); 
    } 

} 

する必要があります！

Answer 1

簡単な方法は、解決策が見つかるまで待つことです。次に、コールツリーのそのブランチをクロールして、成功した移動を記録します。勝利した各コールは、戻り値の先頭にその移動を前置して、それをスタックに戻します。これは次のようなものになります

result = move(rowM + 1, colM); 
if result != "" 
    return "D" + result; // "D" for a move right 
else { 
    // Try a move right ... 

修正するにはいくつかのことがあります。何よりも、あなたは既に取った一歩を踏み出すことを阻む必要があります。今、あなたの検索が行き詰まりに遭うと、それは最後のステップを繰り返し続け、無限の再帰でバックトラックします。

次に、1つの解決策を見つけたら、他の検索を中止するロジックを実装する必要があります。 フィニッシュを設定するとあまり効果がありません。これはローカル変数であり、失敗したか成功したかを呼び出すプログラムに伝える必要があります。

次のステップに進むには十分ですか？