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

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