Recursion-
/*Imagine a robot sitting on the upper left comer of an X by Ygrid. The robot can only
move in two directions: right and down. How many possible paths are there for the
robot to go from (0, 0) to (X, Y) ?
Imagine certain spots are "off limits," such that the robot cannot step on them.
Design an algorithm to find a path for the robot from the top left to the bottom right.
*/
/*This solution will print the path in the reverse order */
/*What happens if there are two paths - This solution will not work ?*/
boolean canmove(x,y) {
if Valid(x,y) return TRUE:
else return FALSE;
}
boolean findpath(int x , int y, ArrayList<Coordinate> path) {
if(x == X-1) || (y ==Y+1){
path.add(Coordinate(x,y));
return TRUE;
}
else if( canmove(x+1,y) && !(canmove(x,y-1)){
if(findpath(x+1,y) {
path.add(x+1,y);
}
}
else if( canmove(x,y-1) && !(canmove(x+1,y)){
if(findpath(x+1,y) {
path.add(x,y-1);
}
}
else {
findpath(x+1,y) ;
findpath(x,y-1);
}
}
Can someone point out the mistake here?
- raady.rockcity December 11, 2014