Show Buttons
Share On Facebook
Share On Twitter
Share On Google Plus
Share On Linkdin
Share On Pinterest
Share On Reddit
Share On Stumbleupon
Contact us
Hide Buttons

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:

NoOfPathObstruction

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));

    }
    }