title: Using DFS to check if a robotic path is possible
body: <p>I am practicing using DFS to solve a robotic path problem. The robot can move only in the following two ways:</p>
  
  <ol>
  <li>(x, y) -> (x, x+y)</li>
  <li>(x, y) -> (x+y, y)</li>
  </ol>
  
  <p>Given a point (10, 12), can the robot arrive at certain point (32, 22)?</p>
  
  <p>I have the following code written, but it does not quite work yet, and it only works for cases like (10, 22), which is the case (x, x+y). If the test case is <strong>(x + (x + y), x+y), e.g. (32, 22)</strong>, my code does not work. I guess I am still confused about using DFS correctly.</p>
  
  <pre><code>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 &amp;&amp; y1 == y2) {
              return true;
          } else if (x1 &gt; x2 &amp;&amp; y1 &gt; y2) {
              return false;
          } else if (x1 &lt; x2 || y1 &gt;= y2) {
              return dfs(x1+y1, y1, x2, y2);
          } else {
              return dfs(x1, x1+y1, x2, y2);
          }
      }
  </code></pre>
  
  <p>When I draw out the graph of the DFS runs, it starts to look like a tree with each node having two children nodes. For example:</p>
  
  <pre><code>  (10, 12)
      /   \
  (10,22) (22, 12)
  </code></pre>
  
  <p>I have also thought about creating an array <code>visited</code> of boolean to indicate whether a node has been visited, but I don't know what the size should be for such an array. </p>
  
  <p>Any help is much appreciated! I really want to get some hands-on using DFS to solve such path problems.</p>
  
  <p>An <strong>alternative</strong> solution I came up with recursion (not DFS though) works as below. In each move, either <code>x2 = x1</code> or <code>y2 = y1</code>. Therefore <code>x1 + y1</code> must be greater than <code>x1</code> or <code>y1</code>, and the 
  this case must always be true: <code>y2 &gt; x2</code> or <code>x2 &gt; y2</code></p>
  
  <pre><code>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 &amp;&amp; y1 == y2) {
              return true;
          } else if (x2 &lt; x1 &amp;&amp; y2 &lt; y1) {
              return false;
          } else {
              if (y2 &gt; x2) {
                  return findPath(x1, y1, x2, y2-x2);
              } else {
                  return findPath(x1, y1, x2-y2, y2);
              }
          }
      }
  </code></pre>