如何在迷宮中追溯...？

所以我正在編寫一個程序，讓一個機器人探索一個迷宮來找到一個指定的洞穴。有四種類型的單元格：洞穴，開始，牆壁和通道。機器人只能移動到通道或洞穴。我實施了我的方法，以便機器人不能移動到訪問的單元格或出界。但一旦移動到沒有有效的相鄰單元的單元格，程序就會停止。那麼，如何讓我的機器人回溯到有效單元的位置？我爲此使用遞歸。以下是我的代碼。任何幫助都會很棒。謝謝！如何在迷宮中追溯...？

public void explore (Cell cavern, Maze maze) throws InterruptedException { 
    // for debugging 
    System.out.println(row + " " + col); 
    System.out.println(cavern.getRow() + " " + cavern.getCol()); 
    System.out.println(visited.toString()); 
    TimeUnit.MILLISECONDS.sleep(10); // delay program 
    //base case 
    if (row == cavern.getRow() && col == cavern.getCol()) { 
     foundCavern = true; 
     return; 
    } 
    else { 
     // move right 
     if ((col+1) < maze.getNumCols() && !visited.contains(maze.getCell(row, col+1)) && (maze.getCell(row, col+1).isPassage() || maze.getCell(row, col+1).isCavern())) { 
      visited.add(maze.getCell(row, col+1)); 
      setRobotLocation(row,col+1); 
      explore(cavern, maze); 
     } 
     // move down 
     else if ((row+1) < maze.getNumRows() && !visited.contains(maze.getCell(row+1, col)) && (maze.getCell(row+1, col).isPassage() || maze.getCell(row+1, col).isCavern())) { 
      visited.add(maze.getCell(row+1, col)); 
      setRobotLocation(row+1,col); 
      explore(cavern, maze); 
     } 
     // move left 
     else if ((col-1) >= 0 && !visited.contains(maze.getCell(row, col-1)) && (maze.getCell(row, col-1).isPassage() || maze.getCell(row, col-1).isCavern())) { 
      visited.add(maze.getCell(row, col-1)); 
      setRobotLocation(row,col-1); 
      explore(cavern, maze); 
     } 
     // move up 
     else if ((row-1) >= 0 && !visited.contains(maze.getCell(row-1, col)) && (maze.getCell(row-1, col).isPassage() || maze.getCell(row-1, col).isCavern())) { 
      visited.add(maze.getCell(row-1, col)); 
      setRobotLocation(row-1,col); 
      explore(cavern, maze); 
     } 
     else { 
      foundCavern = false; 
      return; 
     } 
    } 
}

來源

2014-11-23 JOH

而不是使用遞歸的，它可能是簡單的只是保持你在做的動作一個堆棧。 – azurefrog 2014-11-23 05:11:48

那麼我的訪問列表應該是一個堆棧呢？我有點爲什麼，但你能給我一些更多的細節。像，我應該在哪裏彈出我的代碼？ – JOH 2014-11-23 05:20:14

我認爲你應該擺脫'else'，而是檢查你是否還需要繼續其他方向，這意味着當你從「探索」調用返回時，你仍然沒有找到洞穴 – benji 2014-11-23 05:21:32

我認爲你是在正確的方向。我認爲你應該做的是繼續檢查所有方向，除非你找到了洞穴。由於else子句，您現在正在檢查每次迭代中只有一個方向。因此，當撥打explore時，您無法繼續檢查不同的方向，並且本質上不會回溯。如果你讓你的explore函數返回一個Boolean字段，表示是否到達洞穴更改代碼這樣可以工作：

// move right 
if ... // your condition to check if moving right is possible and you didn't visit 
// code to move right 
found = explore() 
//move down if didn't find cavern 
if (!found) // and moving down is possible and didn't visit 
// code to move down 
found = explore() 
// keep checking other directions

來源

2014-11-23 05:40:44 benji

這很有道理！我試着當我在我的筆記本電腦，並讓我知道如何去。謝謝！ – JOH 2014-11-23 06:36:49

這實際上並不適合我。但我確實得到它的工作。我只需在所有if語句之前保存機器人的位置，並在每次if語句後恢復位置。感謝所有的幫助！對此，我真的非常感激。 – JOH 2014-11-23 20:26:48

對我在探索退貨時遺漏了恢復位置的聲明。它是否與'else'一起工作？還是你必須像我建議的那樣去除它？ – benji 2014-11-23 20:50:38

如何在迷宮中追溯...？

回答

相關問題