Java遞歸問題迷宮

Question

我對Java相當陌生，正試圖用遞歸來解決迷宮問題。我添加了以下代碼的一部分。我有一個包含「字段」的2D數組。牆是1，開始座標和結束座標。

我有一個問題;

我想擦除路徑的位置，只要它不能繼續&末端還沒有達到。我該怎麼做呢？

• 我曾嘗試添加布爾它
• 在遞歸添加迷宮的端[X] [Y] = '0'（空）

但我不它出來了，也許我做錯了。

PS：我已經在論壇上搜索過，閱讀了很多有關遞歸以及其他人如何解決他們的問題，但我無法弄清楚如何解決這個小小的代碼。

-P代表路徑 - 寬度&高度是從二維數組， -I與起始導航（XSTART，ystart）（開始爲什麼我需要嘗試新的位置時，它發現B（開始）

這就是

navigate(int x, int y) {

if (x < 0 || x > width - 1 || y < 0 || y > height - 1) { 
     return; 
    } 
    if (maze[x][y] == '1') { 
     return; 
    } 
    if (maze[x][y] == 'E') { 
     maze[x][y] = 'P'; 
    } 

    if (maze[x][y] == 'P') { 
     return; 
    } 
    if (maze[x][y] == '0') { 
     maze[x][y] = 'P'; 
     return; 
    } 
    if (maze[x][y] == 'B') { 
     maze[x][y] = 'P'; 
     navigate(x + 1, y); 
     navigate(x, y + 1); 
     navigate(x - 1, y); 
     navigate(x, y - 1); 
     return; 
    } 
    maze[x][y] = 'P'; 
    navigate(x + 1, y); 
    navigate(x, y + 1); 
    navigate(x - 1, y); 
    navigate(x, y - 1); 
} 

要放下我做使它工作的事。它已經雖然相當一段時間，但任何人讀它可能會發現它有幫助。

我剛剛創建數組和這些數組數組。每個路徑都是stor ed，只是選擇了一個最大數字，但在理想的情況下，你應該給它長度行*列（因爲這是最大長度）。你找到一個結束後創建一個。

Answer 1

嘗試添加一個ArrayList，其中包含特定遞歸所在的位置，然後一旦您點擊'O'，通過ArrayList並使其上的每個位置成爲最終路徑的'F'。然後，在該方法結束時，清除所有'P（可能通過遍歷2D數組的每個元素）。最後，您有一條或多條由F表示的路徑，這會導致您結束。

我假設'O'是你的結局位置。

Answer 2

你唯一需要的標記是：

1 - wall 
0 - empty (can use for path) 
P - path 

現在，讓我們開始在起點導航：

navigate(xstart, ystart); 

我們該如何定位？

navigate(int x, int y) { 

    // Are we there yet? 
    if (x == xend && y == yend) { 
     // Yay! We're here! And our path is marked with P's 
     // However, you're many levels inside the recursion. How to break out? 
     // Easiest way - throw an exception, and catch in the original caller 
    } 

    // Don't step where you're not supposed to 
    if (x < 0 || x > width - 1 || y < 0 || y > height - 1) { 
     return; 
    } 
    if (maze[x][y] == '1' || maze[x][y] == 'p') { 
     return; 
    } 

    // OK, we can step through here. Let's mark this place as path 
    maze[x][y] = 'P'; 

    // Now, let's try continuing to neighboring squares 
    navigate(x + 1, y); 
    navigate(x, y + 1); 
    navigate(x - 1, y); 
    navigate(x, y - 1); 

    // If we're still here, guess this square is not on the path - remove it 
    maze[x][y] = '0'; 
} 

（警告：沒有測試的代碼，我就是一個C＃程序員 - 但它應該是相同的）

趣味測試：如果

• 會發生什麼你改變了遞歸調用的順序navigate()？
• 如果牆壁很少，會怎麼樣？這個算法如何使用這個空間？

遞歸很有趣！你可以得到一個真正的麻袋溢出！