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

我正在练习使用DFS解决机器人路径问题。机器人可在以下两种方式只能移动：使用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必须大于或x1y1和这种情况下，必须是真实的：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); 
      } 
     } 
    }

来源

2016-10-02 TonyGW

'return true'和'return false' branch look（almost！）right，但在所有其他情况下，您实际上需要考虑两种选择;您必须在每个节点中调用'dfs' *两次*。 – 2016-10-02 19:24:13

试试这个。

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); 
}

来源

2016-10-02 20:38:10 saka1029

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

回答

相关问题