0

我对Java相当陌生，正在尝试用递归解决迷宫。我在下面添加了部分代码。我有一个包含“字段”的二维数组。墙为 1，给出起始坐标和结束坐标。

我有一个问题；

每当路径无法继续且未达到终点时，我想删除路径的位置。我该怎么做呢？

  • 我已经尝试为它添加布尔值
  • 在递归结束时添加一个 maze[x][y] = '0' (empty)

但我还想不通，也许我做错了。

PS：我在论坛上搜索过，阅读了很多关于递归以及其他人如何解决他们的问题的信息，但我不知道如何修复这一点代码。

-P 代表路径 - 宽度和高度来自 2D 数组，-我从开始 navigation(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);
}

打算放下我为使它工作而做的事情。虽然已经有一段时间了，但任何阅读它的人可能会发现它很有帮助。

我刚刚创建了数组和这些数组的数组。在存储每个路径的位置，只需选择一个最大数量，但在理想情况下，您应该为其指定长度行 * 列（因为这是最大长度）。在找到结束后创建一个。

4

2 回答 2

0

尝试添加一个包含特定递归位置的 ArrayList，然后一旦你点击“O”，就通过 ArrayList 并将其上的每个位置设置为最终路径的“F”。然后，在方法结束时，清除所有“P”（可能通过遍历 2D 数组的每个元素）最后，您有一条或多条用 F 表示的路径将您带到终点。

我假设'O'是你的结束位置。

于 2013-03-21T15:39:45.573 回答
0

您需要的唯一标记是：

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()调用的顺序会发生什么？
  • 如果只有几堵墙怎么办？这个算法将如何使用空间？

递归很有趣！你可以得到一个真正的 Sack Overflow！

于 2013-03-21T16:03:55.930 回答