Count number of ways to reach destination in a maze | Java implementation of the approach ; Function to return the count of possible paths in a maze [ R ] [ C ] from ( 0 , 0 ) to ( R - 1 , C - 1 ) that do not pass through any of the marked cells ; If the initial cell is blocked , there is no way of moving anywhere ; Initializing the leftmost column ; If we encounter a blocked cell in leftmost row , there is no way of visiting any cell directly below it . ; Similarly initialize the topmost row ; If we encounter a blocked cell in bottommost row , there is no way of visiting any cell directly below it . ; The only difference is that if a cell is - 1 , simply ignore it else recursively compute count value maze [ i ] [ j ] ; If blockage is found , ignore this cell ; If we can reach maze [ i ] [ j ] from maze [ i - 1 ] [ j ] then increment count . ; If we can reach maze [ i ] [ j ] from maze [ i ] [ j - 1 ] then increment count . ; If the final cell is blocked , output 0 , otherwise the answer ; Function to return the count of all possible paths from ( 0 , 0 ) to ( n - 1 , m - 1 ) ; We have to calculate m + n - 2 C n - 1 here which will be ( m + n - 2 ) ! / ( n - 1 ) ! ( m - 1 ) ! ; Function to return the total count of paths from ( 0 , 0 ) to ( n - 1 , m - 1 ) that pass through at least one of the marked cells ; Total count of paths - Total paths that do not pass through any of the marked cell ; return answer ; Driver code
import java . io . * ; class GFG { static int R = 4 ; static int C = 4 ; static int countPaths ( int maze [ ] [ ] ) { if ( maze [ 0 ] [ 0 ] == - 1 ) return 0 ; for ( int i = 0 ; i < R ; i ++ ) { if ( maze [ i ] [ 0 ] == 0 ) maze [ i ] [ 0 ] = 1 ; else break ; } for ( int i = 1 ; i < C ; i ++ ) { if ( maze [ 0 ] [ i ] == 0 ) maze [ 0 ] [ i ] = 1 ; else break ; } for ( int i = 1 ; i < R ; i ++ ) { for ( int j = 1 ; j < C ; j ++ ) { if ( maze [ i ] [ j ] == - 1 ) continue ; if ( maze [ i - 1 ] [ j ] > 0 ) maze [ i ] [ j ] = ( maze [ i ] [ j ] + maze [ i - 1 ] [ j ] ) ; if ( maze [ i ] [ j - 1 ] > 0 ) maze [ i ] [ j ] = ( maze [ i ] [ j ] + maze [ i ] [ j - 1 ] ) ; } } return ( maze [ R - 1 ] [ C - 1 ] > 0 ) ? maze [ R - 1 ] [ C - 1 ] : 0 ; } static int numberOfPaths ( int m , int n ) { int path = 1 ; for ( int i = n ; i < ( m + n - 1 ) ; i ++ ) { path *= i ; path /= ( i - n + 1 ) ; } return path ; } static int solve ( int maze [ ] [ ] ) { int ans = numberOfPaths ( R , C ) - countPaths ( maze ) ; return ans ; } public static void main ( String [ ] args ) { int maze [ ] [ ] = { { 0 , 0 , 0 , 0 } , { 0 , - 1 , 0 , 0 } , { - 1 , 0 , 0 , 0 } , { 0 , 0 , 0 , 0 } } ; System . out . println ( solve ( maze ) ) ; } }