Tuesday, July 26, 2011

Find The Number of Unique Path in Maze Where Robot is Sitting at Top-Left Corner & Can Move According to Given Constraints

A robot is located at the top-left corner of a m x n grid (marked ‘Start’ in the diagram below). The robot can only move either down or right at any point in time. The robot is trying to reach the bottom-right corner of the grid . marked ‘end' in the diagram below.How many possible unique paths are there?

I posted the solution with post because i was aware of such problem earlier :)

Basic Solution,Approach,Algoriothms Using BackTracing

Start form top left corner (say we are at position 1,1 in starting deonted by row=r,column=c (e.g. r=1, c=1 initially) & then will will keep moving untill reach when r=m and c=n e.g. bottom-left corner) writing code for this is simple.

int backtrack(int r, int c, int m, int n) {
if (r == m && c == n)
return 1;
if (r > m || c > n)
return 0;

return backtrack(r+1, c, m, n) + backtrack(r, c+1, m, n);
}

but as normal backtracking problems it inovolves repeated calculations
so is very inefficient in the sense that it recalculates the same solutio n over patah again & again. so we need to use a dynamic programming (DP) technique called memoization akso called top down approach.

const int M_MAX = 10;
const int N_MAX = 10;

int backtrack(int r, int c, int m, int n, int mat[][N_MAX+2]) {
if (r == m && c == n)
return 1;
if (r > m || c > n)
return 0;

if (mat[r+1][c] == -1)
mat[r+1][c] = backtrack(r+1, c, m, n, mat);
if (mat[r][c+1] == -1)
mat[r][c+1] = backtrack(r, c+1, m, n, mat);

return mat[r+1][c] + mat[r][c+1];
}

int bt(int m, int n) {
int mat[M_MAX][N_MAX];
memset(mat, -1, sizeof(mat));
return backtrack(1, 1, m, n, mat);
}

Time Complexity O(M+N)
Space Complexity O(M*N)



Bottom-Up Dynamic Programming More Efficient

As we know The total unique paths at above matrix (r,c) is equal to the sum of total unique paths from matrix to the right (r,c+1) and the matrix below (r+1,c).

(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)!)..

const int M_MAX = 100;
const int N_MAX = 100;

int dp(int m, int n) {
int mat[M_MAX][N_MAX] = {0};
mat[m][n+1] = 1;

for (int r = m; r >= 1; r--)
for (int c = n; c >= 1; c--)
mat[r][c] = mat[r+1][c] + mat[r][c+1];

return mat[1][1];
}

Lets Assume you have M×N sample matrix or grid. so it doen't matter how you traverse the grids, you always traverse a total of M steps. To be more exact, you always have to choose M-N steps to the right (R) and N steps to the bottom (B). Therefore, the problem can be transformed to a question of how many ways can you choose M-N R‘s and N B‘s in these M+N-2 steps. The answer is C(M,N) (or C(M,M-N)). Therefore, the general solution for a m x n grid is C(m+n-2, m-1) & this is our answer.

Time Complexity O(M*N)
Space Complexity O(M*N)


Follow Up: Using Above We Have Only Calculated the number of paths can we print those path as well if yes what will be time complexity.

1 comment :

Anonymous said...

hi i found this solution on website <a href="mycareerstack.com>mycareerstack.com</a>. you can refer to this website for further details.


<br/><br/>
Backtracking Solution:

The most direct way is to write code that traverses each possible path, which can be done using backtracking. When you reach row=m and col=n, you know you’ve reached the bottom-right corner, and there is one additional unique path to it. However, when you reach row > m or col > n, then it’s an invalid path and you should stop traversing. For any grid at row=r and col=c, you have two choices:

Traverse to the right or traverse to the bottom. Therefore, the total unique paths at grid (r,c) is equal to the sum of total unique paths from the grid to the right and the grid below.
<p>
int backtrack(int r, int c, int m, int n) {
if (r == m && c == n)
return 1;
if (r > m || c > n)
return 0;

return backtrack(r+1, c, m, n) + backtrack(r, c+1, m, n);
}
</p>

The other solution would be using Dynamic approach in a top down approach. The total unique paths at grid (i,j) is equal to the sum of total unique paths from grid to the right (i,j+1) and the grid below (i+1,j)
<p>
int uniquePaths(int row, int col)
{
int matrix[row][col];

// set the initial conditions
for(int i=0;i < row;i++)
matrix[i][col-1]=1;
for(int i=0;i < col;i++)
matrix[row-1][i]=1;
// theres no path when we have reached
// the destination
matrix[i][j]=0;

for (int i = row-2; i >= 0; i--)
{
for (int j = col-2; j >= 0; j--)
{
matrix[i][j] = matrix[i+1][j] + matrix[i][j+1];
}
}
return matrix[0][0];
}
</p>

The last and the most efficient solution would be using combinatorics. In 7×3 sample grid no matter how we traverse the grids, we always traverse a total of 8 steps. To be exact, we always have to choose 6 steps to the right (R) and 2 steps to the bottom (B). Therefore, the problem can be transformed to a question of how many ways can you choose 6R‘s and 2B‘s in these 8 steps. The answer is C(8,2) (or C(8,6)). Therefore, the general solution for a m x n grid is C(m+n-2, m-1).

Food for thought:
What would you do if some obstacles are added to the grids marked as ‘X’, such that you cannot go through the obstacles? How many unique paths would there be?

In this case giving a combinatorics answer becomes very tricky, however dynamic programming would still work. If the point matrix[i][j] is marked with ‘X’ then there is no way of reaching that point because we cannot go there and that matrix[i][j] would be set to 0 and not matrix[i+1][j] + matrix[i][j+1].