Dynamic Programming — Count all paths in 2D Matrix with Obstructions in it

Objec­tive: Given two dimen­sional matrix, write an algo­rithm to count all pos­si­ble paths from top left cor­ner to bottom-right cor­ner. You are allowed to move only in two direc­tions, move right OR move down. There are few obstruc­tions as well, means few cells are blocked and you can­not travel that cell.

Many times this prob­lem is being referred as “Robot Travel Prob­lem”. Given a 2d matrix, how many ways a robot can travel from top left cor­ner to bot­tom right cor­ner and there are few cells in which robot can­not travel.

Exam­ple:

Approach:

• This prob­lem is the exten­sion of the prob­lem “Count all paths from top left to bot­tom right of a mXn matrix”.
• All we need to take care if one extra con­di­tion that we can­not travel to the blocked cells.
• In recur­sive solu­tion given in “Count all paths from top left to bot­tom right of a mXn matrix” just check for con­di­tion if cell is not blocked.
• In Dynamic pro­gram­ming solu­tion, we need to take care of two con­di­tions, first we are not solv­ing it for blocked cells and while solv­ing for other cells do not involve blocked cells.
• See the code for bet­ter understanding.

Code:

Out­put:

```No Of Path (Recursion):- 1
No Of Path (DP):- 1
```

You may also like...

• mrben7

//here is my solu­tion using top down approach : at each stage my pro­gram counts the num­ber of paths from the cur­rent point
A(i,j) to the des­ti­na­tion D(rows-1,cols-1)
//
the num­ber of ways to go from des­ti­na­tion ti itself is 0 if the
des­ti­na­tion is blocked,and 1 if the des­ti­na­tion is not blocked

import java.util.Scanner;

pub­lic class pathsCounter {

pub­lic sta­tic int countPaths(int[][] matrix) {

int rows = matrix.length ;
int cols = matrix[0].length ;
if(matrix[rows-1][cols-1]==-1) return 0 ; // the des­ti­na­tion is unreach­able so there is no path
int sol[][] = new int[rows][cols] ;
sol[rows-1][cols-1] = 1 ; // there is only one path that is going from des­ti­na­tion to itself
//for(int i= 0;i<rows;i++) if(matrix[i][cols-1] != –1) sol[i][cols-1] = 1 ;
//for(int i= 0;i=0;j–)
for(int i= rows-1;i>=0;i–)
if(matrix[i][j] != –1) {
if(i!=rows-1 || j!=cols-1) {
if(i == rows-1) sol[i][j] = sol[i][j+1] ;
else if(j== cols-1) sol[i][j] = sol[i+1][j] ;
else sol[i][j] = sol[i][j+1] + sol[i+1][j] ;

}
}

return sol[0][0] ;
}

pub­lic sta­tic void main(String []args){
Scan­ner input = new Scanner(System.in) ;
int[][] matrix = {{1,1,1},{1,-1,-1},{1,-1,1}} ;
System.out.println(countPaths(matrix));

}
}