Paths of a robot

Consider a point P(n,n) in the cartesian co-ordinate system
A robot has to start from the origin and reach this point. The only steps
the robot can take are :
1 unit right
1 unit up.

How many different paths can the robot take to point P.
Is there an optimal path to point P. (both up and right steps incur the same
cost).

Answer:


/*
* Paths to (x,y) = Paths to the previous point to left i.e (x-1,y) +
* Paths to the point below i.e (x, y-1) +
* two paths from (x-1, y) and (x,y-1)
* */
int Getpaths(Point p)
{
int paths = 0;
if ( y > 0 )
paths += Getpaths( Point(p.x, p.y -1) ) + 1;
if ( x > 0 )
paths += Getpaths( Point(p.x-1, p.y) ) + 1;
return paths;
}

No comments: