Count number of ways to reach destination in a Maze | Python 3 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
R = 4 NEW_LINE C = 4 NEW_LINE def countPaths ( maze ) : NEW_LINE INDENT if ( maze [ 0 ] [ 0 ] == - 1 ) : NEW_LINE INDENT return 0 NEW_LINE DEDENT for i in range ( R ) : NEW_LINE INDENT if ( maze [ i ] [ 0 ] == 0 ) : NEW_LINE INDENT maze [ i ] [ 0 ] = 1 NEW_LINE DEDENT else : NEW_LINE INDENT break NEW_LINE DEDENT DEDENT for i in range ( 1 , C , 1 ) : NEW_LINE INDENT if ( maze [ 0 ] [ i ] == 0 ) : NEW_LINE INDENT maze [ 0 ] [ i ] = 1 NEW_LINE DEDENT else : NEW_LINE INDENT break NEW_LINE DEDENT DEDENT for i in range ( 1 , R , 1 ) : NEW_LINE INDENT for j in range ( 1 , C , 1 ) : NEW_LINE INDENT if ( maze [ i ] [ j ] == - 1 ) : NEW_LINE INDENT continue NEW_LINE DEDENT if ( maze [ i - 1 ] [ j ] > 0 ) : NEW_LINE INDENT maze [ i ] [ j ] = ( maze [ i ] [ j ] + maze [ i - 1 ] [ j ] ) NEW_LINE DEDENT if ( maze [ i ] [ j - 1 ] > 0 ) : NEW_LINE INDENT maze [ i ] [ j ] = ( maze [ i ] [ j ] + maze [ i ] [ j - 1 ] ) NEW_LINE DEDENT DEDENT DEDENT if ( maze [ R - 1 ] [ C - 1 ] > 0 ) : NEW_LINE INDENT return maze [ R - 1 ] [ C - 1 ] NEW_LINE DEDENT else : NEW_LINE INDENT return 0 NEW_LINE DEDENT DEDENT if __name__ == ' _ _ main _ _ ' : NEW_LINE INDENT maze = [ [ 0 , 0 , 0 , 0 ] , [ 0 , - 1 , 0 , 0 ] , [ - 1 , 0 , 0 , 0 ] , [ 0 , 0 , 0 , 0 ] ] NEW_LINE print ( countPaths ( maze ) ) NEW_LINE DEDENT