使用 DFS 检查机器人路径是否可行

Question

我正在练习使用 DFS 解决机器人路径问题。机器人只能通过以下两种方式移动：

(x, y) -> (x, x+y)
(x, y) -> (x+y, y)

给定一个点(10, 12)，机器人能否到达某个点(32, 22)？

我写了下面的代码，但是还不太行得通，而且只对(10, 22)这样的情况有效，也就是(x, x+y)。如果测试用例是 (x + (x + y), x+y)，例如(32, 22)，我的代码不起作用。我想我仍然对正确使用 DFS 感到困惑。

public boolean canReach(int x1, int y1, int x2, int y2) {
        return dfs(x1, y1, x2, y2);
    }

    private boolean dfs(int x1, int y1, int x2, int y2) {

        if (x1 == x2 && y1 == y2) {
            return true;
        } else if (x1 > x2 && y1 > y2) {
            return false;
        } else if (x1 < x2 || y1 >= y2) {
            return dfs(x1+y1, y1, x2, y2);
        } else {
            return dfs(x1, x1+y1, x2, y2);
        }
    }

当我画出 DFS 运行图时，它开始看起来像一棵树，每个节点都有两个子节点。例如：

  (10, 12)
    /   \
(10,22) (22, 12)

我也想过创建一个布尔数组visited来指示是否访问过一个节点，但我不知道这样的数组的大小应该是多少。

非常感谢任何帮助！我真的很想动手使用 DFS 来解决此类路径问题。

我提出的递归（虽然不是 DFS）的替代解决方案如下所示。在每一步中，要么 x2 = x1 要么 y2 = y1。因此 x1 + y1 必须大于 x1 或 y1，并且这种情况必须始终为真：y2 > x2 或 x2 > y2

public boolean canReach2(int x1, int y1, int x2, int y2) {
        return findPath(x1, y1, x2, y2);
    }

    private boolean findPath(int x1, int y1, int x2, int y2) {
        if (x1 == x2 && y1 == y2) {
            return true;
        } else if (x2 < x1 && y2 < y1) {
            return false;
        } else {
            if (y2 > x2) {
                return findPath(x1, y1, x2, y2-x2);
            } else {
                return findPath(x1, y1, x2-y2, y2);
            }
        }
    }

Answer 1

试试这个。

public boolean findPath(int x1, int y1, int x2, int y2) {
    if (x1 == x2 && y1 == y2)
        return true;
    else if (x1 > x2 || y1 > y2)
        return false;
    else
        return x1 > 0 && findPath(x1, x1 + y1, x2, y2)
            || y1 > 0 && findPath(x1 + y1, y1, x2, y2);
}

使用 DFS 检查机器人路径是否可行

Using DFS to check if a robotic path is possible

java

algorithm

depth-first-search