Count number of ways to reach destination in a Maze | PHP program to count number of paths in a maze with obstacles . ; Returns count of possible paths in a maze [ R ] [ C ] from ( 0 , 0 ) to ( R - 1 , C - 1 ) ; 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 ; Driver Code
< ? php $ R = 4 ; $ C = 4 ; function countPaths ( $ maze ) { global $ R , $ C ; if ( $ maze [ 0 ] [ 0 ] == - 1 ) return 0 ; for ( $ i = 0 ; $ i < $ R ; $ i ++ ) { if ( $ maze [ $ i ] [ 0 ] == 0 ) $ maze [ $ i ] [ 0 ] = 1 ; else break ; } for ( $ i = 1 ; $ i < $ C ; $ i ++ ) { if ( $ maze [ 0 ] [ $ i ] == 0 ) $ maze [ 0 ] [ $ i ] = 1 ; else break ; } for ( $ i = 1 ; $ i < $ R ; $ i ++ ) { for ( $ 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 ; } $ maze = array ( array ( 0 , 0 , 0 , 0 ) , array ( 0 , -1 , 0 , 0 ) , array ( -1 , 0 , 0 , 0 ) , array ( 0 , 0 , 0 , 0 ) ) ; echo countPaths ( $ maze ) ; ? >