java - 基本递归回溯(机器人二维寻路)

Question

我正在解决一道练习题，但遇到了困难。该问题要求编写一个方法，该方法接受两个整数 x 和 y，通过重复使用三个移动之一来打印在 2D 平面中从 (0,0) 到 (x,y) 行进的所有解决方案:

• 向右移动 1 (E)
• 向上移动 1 (N)
• 向右移动 1 并向上移动 1(NE)

这些是一些示例调用:

• 调用:旅行(2, 1)
• 输出:E E N//E N E//E NE//N E E//NE E

我编写了以下代码:

public void travel(int x, int y) {
    if (x == 0 && y == 0) {
        System.out.println();
    } else if (x > 0 && y > 0) {
        System.out.print("E ");
        travel(x-1, y);
        System.out.print("N ");
        travel(x, y-1);
        System.out.print("NE ");
        travel(x-1, y-1);
    } else if (x > 0 && y == 0) {
        System.out.print("E ");
        travel(x-1, y);
    } else if (y > 0 && x == 0) {
        System.out.print("N ");
        travel(x, y-1);
    }
}

调用上述方法会产生以下代码:

• 调用:旅行(2,1);
• 输出:E E N//N E//NE//N E E//NE E

我知道对于这个示例调用，问题在于 E 仅在需要 E 的三种不同情况下打印一次，因为 E 是在调用后续递归方法之前打印的。

我想通过在每次调用 Travel 方法时附加 System.out.print 命令来解决此问题(不确定这是正确的方法)。这样，每当调用旅行方法时，每次都会打印结果的第一个字母。但是，由于该方法不返回任何内容，因此我无法在 print 语句中插入该方法。这是我被困了很长时间的地方。

任何关于如何从这里开始的建议将不胜感激。

Answer 1

递归构建解决方案时，通常会将部分构建的解决方案作为参数传递给递归调用。

public void travel(int x, int y, String path) {
    if (x == 0 && y == 0) {
        System.out.println(path);
    } else if (x > 0 && y > 0) {
        travel(x-1, y, path + ' E');
        travel(x, y-1, path + ' N');
        travel(x-1, y-1, path + ' NE');
    } else if (x > 0 && y == 0) {
        travel(x-1, y, path + ' E');
    } else if (y > 0 && x == 0) {
        travel(x, y-1, path + ' N');
    }
}

看看我们如何在前进时构建路径 - 并让函数调用处理记住我们在搜索中的位置的复杂性？这还有一个好处就是可以简化我们的代码，因为每个路径我们只调用一次 System.out.println。