TonyGW TonyGW - 2 months ago 10
Java Question

Using DFS to check if a robotic path is possible

I am practicing using DFS to solve a robotic path problem. The robot can move only in the following two ways:


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

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



Given a point (10, 12), can the robot arrive at certain point (32, 22)?

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 (x + (x + y), x+y), e.g. (32, 22), my code does not work. I guess I am still confused about using DFS correctly.

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


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:

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


I have also thought about creating an array
visited
of boolean to indicate whether a node has been visited, but I don't know what the size should be for such an array.

Any help is much appreciated! I really want to get some hands-on using DFS to solve such path problems.

An alternative solution I came up with recursion (not DFS though) works as below. In each move, either
x2 = x1
or
y2 = y1
. Therefore
x1 + y1
must be greater than
x1
or
y1
, and the
this case must always be true:
y2 > x2
or
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

Try this.

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