**Objective: **Given two dimensional matrix, write an algorithm to count all possible paths from top left corner to bottom-right corner. You are allowed to move only in two directions, move right OR move down. There are few obstructions as well, means few cells are blocked and you cannot travel that cell.

Many times this problem is being referred as “** Robot Travel Problem**“. Given a 2d matrix, how many ways a robot can travel from top left corner to bottom right corner and there are few cells in which robot cannot travel.

**Example**:

**Approach:**

- This problem is the extension of the problem “Count all paths from top left to bottom right of a mXn matrix“.
- All we need to take care if one extra condition that we cannot travel to the blocked cells.
- In recursive solution given in “Count all paths from top left to bottom right of a mXn matrix” just check for condition if cell is not blocked.
- In Dynamic programming solution, we need to take care of two conditions, first we are not solving it for blocked cells and while solving for other cells do not involve blocked cells.
- See the code for better understanding.

**Code:**

This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.

Learn more about bidirectional Unicode characters

public class NoOfPathObstruction { | |

public int count(int [][] arrA, int row, int col){ | |

//base case | |

//check if last cell is reached since after that only one path | |

if(row==arrA.length–1 && col==arrA.length–1){ | |

return 1; | |

} | |

int right =0; | |

int down = 0; | |

if(row!=arrA.length–1 && arrA[row+1][col]!=–1){ | |

right = count(arrA, row+1, col); | |

} | |

if(col!=arrA.length–1 && arrA[row][col+1]!=–1){ | |

down = count(arrA, row, col+1); | |

} | |

return right + down; | |

} | |

public int countDP(int [][] arrA){ | |

int result [][] = arrA; | |

for (int i = 1; i <result.length ; i++) { | |

for (int j = 1; j <result.length ; j++) { | |

if(result[i][j]!=–1){ | |

result[i][j]=0; | |

if(result[i–1][j]>0) | |

result[i][j]+=result[i–1][j]; | |

if(result[i][j–1]>0) | |

result[i][j]+=result[i][j–1]; | |

} | |

} | |

} | |

return result[arrA.length–1][arrA.length–1]; | |

} | |

public static void main(String[] args) { | |

int arrA [][] = {{1,1,1},{1,–1,1},{1,–1,1}}; | |

NoOfPathObstruction noOfPaths = new NoOfPathObstruction(); | |

System.out.println("No Of Path (Recursion):- " +noOfPaths.count(arrA,0,0)); | |

System.out.println("No Of Path (DP):- " +noOfPaths.countDP(arrA)); | |

} | |

} |

**Output:**

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

//here is my solution using top down approach : at each stage my program counts the number of paths from the current point

A(i,j) to the destination D(rows-1,cols-1)

//

the number of ways to go from destination ti itself is 0 if the

destination is blocked,and 1 if the destination is not blocked

import java.util.Scanner;

public class pathsCounter {

public static int countPaths(int[][] matrix) {

int rows = matrix.length ;

int cols = matrix[0].length ;

if(matrix[rows-1][cols-1]==-1) return 0 ; // the destination is unreachable 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 destination 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] ;

}

public static void main(String []args){

Scanner input = new Scanner(System.in) ;

int[][] matrix = {{1,1,1},{1,-1,-1},{1,-1,1}} ;

System.out.println(countPaths(matrix));

}

}