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()？
• 如果墙壁很少，会怎么样？这个算法如何使用这个空间？

递归很有趣！你可以得到一个真正的麻袋溢出！