WAP to Solve Robot In The Maze

Pretend there is a robot that has to navigate a maze (N x M). The robot can only move down or right and the maze can contain walls. Write an algorithm to determine the number of paths the robot can take.

1st Approach No of Paths

(For clarity, we will solve this part assuming an X*Y Matrix)
Each path has (X-1)+(Y-1) steps. Imagine the following paths:

X X Y Y X (move right -> right -> down -> down -> right)
X Y X Y X (move right -> down -> right -> down -> right)
...& so on

Each path can be fully represented by the moves at which we move
right. That is, if I were to ask you which path you took, you could
simply say “I moved right on step 3 and 4.”
Since you must always move right X-1 times, and you have X-1 + Y-1
total steps, you have to pick X-1 times to move right out of X-1+Y-1
choices. Thus, there are C(X-1, X-1+Y-1) paths (e.g., X-1+Y-1 choose
X-1):

(X-1 + Y-1)! / ((X-1)! * (Y-1)!)..Hope This Equation Clear to Every1

which is nothing but C(2n-2,n-1) Catalan Number

2nd Approach

DP(Always Best)

A robot can take path (N,M) from either (N-1,M) or (N,M-1)
if N and M is 0, its the beginning so return 0.
if N or M is 0, we can get there in 1 path.

We call paths(N,M) with s[][] initialized to -1.

int paths(int i,int j)
{
if(!(i||j)) //means we either can go down or right path as only 1 is
zero
return 1;

if((i&&j))/// no path exist if both are zero
return 0;

if(s[i][j] != -1)
return s[i][j];

s[i][j] = paths(i-1,j) + paths(i,j-1);

return s[i][j];

}

Running C++ Code


#include
void PrintRobotPaths(std::string path, int row, int column, int totrows, int totcols)
{
if(column == totcols && row == totrows)
{
std::cout << path << std::endl;
return;
}
if(row == totrows)
{
std::string pc = path + " D";
PrintRobotPaths(pc, row, column+1, totrows, totcols);
return;
}
if(column == totcols)
{
std::string pr = path + " R";
PrintRobotPaths(pr, row+1, column, totrows, totcols);
return;
}
std::string pr = path + " R";
std::string pc = path + " D";
PrintRobotPaths(pr, row+1, column, totrows, totcols);
PrintRobotPaths(pc, row, column+1, totrows, totcols);
}



int main(int argc, char** argv)
{
int row=4;
int column=4;
std::string path;
PrintRobotPaths(path,1, 1, row, column);
return 0;
}


Run Here https://ideone.com/qq7dh