TonyGW - 2 months ago 10

Java Question

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

- (x, y) -> (x, x+y)
- (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

`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`

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

An

`x2 = x1`

`y2 = y1`

`x1 + y1`

`x1`

`y1`

this case must always be true:

`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

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

Source (Stackoverflow)

Comments