Print all paths from a source point to all the 4 corners of a Matrix | Function to check if we reached on of the entry / exit ( corner ) point . ; Function to check if the index is within the matrix boundary . ; Recursive helper function ; If any corner is reached push the string t into ans and return ; For all the four directions ; The new ith index ; The new jth index ; The direction R / L / U / D ; If the new cell is within the matrix boundary and it is not previously visited in same path ; mark the new cell visited ; Store the direction ; Backtrack to explore other paths ; Function to find all possible paths ; Create a direction array for all the four directions ; stores the result ; Initialise variable ; function call ; Print the result
def isCorner ( i , j , M , N ) : NEW_LINE INDENT if ( ( i == 0 and j == 0 ) or ( i == 0 and j == N - 1 ) or ( i == M - 1 and j == N - 1 ) or ( i == M - 1 and j == 0 ) ) : NEW_LINE INDENT return True NEW_LINE DEDENT return False NEW_LINE DEDENT def isValid ( i , j , M , N ) : NEW_LINE INDENT if ( i < 0 or i >= M or j < 0 or j >= N ) : NEW_LINE INDENT return False NEW_LINE DEDENT return True NEW_LINE DEDENT def solve ( i , j , M , N , Dir , maze , t , ans ) : NEW_LINE INDENT if ( isCorner ( i , j , M , N ) ) : NEW_LINE INDENT ans . append ( t ) NEW_LINE return NEW_LINE DEDENT for k in range ( 4 ) : NEW_LINE INDENT x = i + Dir [ k ] [ 0 ] NEW_LINE y = j + Dir [ k ] [ 1 ] NEW_LINE c = Dir [ k ] [ 2 ] NEW_LINE if ( isValid ( x , y , M , N ) and maze [ x ] [ y ] == 1 ) : NEW_LINE INDENT maze [ x ] [ y ] = 0 NEW_LINE t += c NEW_LINE solve ( x , y , M , N , Dir , maze , t , ans ) NEW_LINE t = t [ : len ( t ) - 1 ] NEW_LINE maze [ x ] [ y ] = 1 NEW_LINE DEDENT DEDENT return NEW_LINE DEDENT def possiblePaths ( src , maze ) : NEW_LINE INDENT Dir = [ [ - 1 , 0 , ' U ' ] , [ 0 , 1 , ' R ' ] , [ 1 , 0 , ' D ' ] , [ 0 , - 1 , ' L ' ] ] NEW_LINE temp = " " NEW_LINE ans = [ ] NEW_LINE solve ( src [ 0 ] , src [ 1 ] , len ( maze ) , len ( maze [ 0 ] ) , Dir , maze , temp , ans ) NEW_LINE return ans NEW_LINE DEDENT maze = [ [ 1 , 0 , 0 , 1 , 0 , 0 , 1 , 1 ] , [ 1 , 1 , 1 , 0 , 0 , 0 , 1 , 0 ] , [ 1 , 0 , 1 , 1 , 1 , 1 , 1 , 0 ] , [ 0 , 0 , 0 , 0 , 1 , 0 , 0 , 0 ] , [ 1 , 0 , 1 , 0 , 1 , 0 , 0 , 1 ] , [ 0 , 1 , 1 , 1 , 1 , 0 , 0 , 1 ] , [ 0 , 1 , 0 , 0 , 1 , 1 , 1 , 1 ] , [ 1 , 1 , 0 , 0 , 0 , 0 , 0 , 1 ] ] NEW_LINE src = [ 4 , 2 ] NEW_LINE paths = possiblePaths ( src , maze ) NEW_LINE if ( len ( paths ) == 0 ) : NEW_LINE INDENT print ( " No ▁ Possible ▁ Paths " ) NEW_LINE DEDENT else : NEW_LINE INDENT for i in paths : NEW_LINE INDENT print ( i ) NEW_LINE DEDENT DEDENT