Rat in a Maze Problem when movement in all possible directions is allowed | Python3 implementation of the above approach ; Function returns true if the move taken is valid else it will return false . ; Function to print all the possible paths from ( 0 , 0 ) to ( n - 1 , n - 1 ) . ; This will check the initial point ( i . e . ( 0 , 0 ) ) to start the paths . ; If reach the last cell ( n - 1 , n - 1 ) then store the path and return ; Mark the cell as visited ; Check if downward move is valid ; Check if the left move is valid ; Check if the right move is valid ; Check if the upper move is valid ; Mark the cell as unvisited for other possible paths ; Function to store and print all the valid paths ; vector to store all the possible paths ; Call the utility function to find the valid paths ; Print all possible paths ; Driver code
from typing import List NEW_LINE MAX = 5 NEW_LINE def isSafe ( row : int , col : int , m : List [ List [ int ] ] , n : int , visited : List [ List [ bool ] ] ) -> bool : NEW_LINE INDENT if ( row == - 1 or row == n or col == - 1 or col == n or visited [ row ] [ col ] or m [ row ] [ col ] == 0 ) : NEW_LINE INDENT return False NEW_LINE DEDENT return True NEW_LINE DEDENT def printPathUtil ( row : int , col : int , m : List [ List [ int ] ] , n : int , path : str , possiblePaths : List [ str ] , visited : List [ List [ bool ] ] ) -> None : NEW_LINE INDENT if ( row == - 1 or row == n or col == - 1 or col == n or visited [ row ] [ col ] or m [ row ] [ col ] == 0 ) : NEW_LINE INDENT return NEW_LINE DEDENT if ( row == n - 1 and col == n - 1 ) : NEW_LINE INDENT possiblePaths . append ( path ) NEW_LINE return NEW_LINE DEDENT visited [ row ] [ col ] = True NEW_LINE if ( isSafe ( row + 1 , col , m , n , visited ) ) : NEW_LINE INDENT path += ' D ' NEW_LINE printPathUtil ( row + 1 , col , m , n , path , possiblePaths , visited ) NEW_LINE path = path [ : - 1 ] NEW_LINE DEDENT if ( isSafe ( row , col - 1 , m , n , visited ) ) : NEW_LINE INDENT path += ' L ' NEW_LINE printPathUtil ( row , col - 1 , m , n , path , possiblePaths , visited ) NEW_LINE path = path [ : - 1 ] NEW_LINE DEDENT if ( isSafe ( row , col + 1 , m , n , visited ) ) : NEW_LINE INDENT path += ' R ' NEW_LINE printPathUtil ( row , col + 1 , m , n , path , possiblePaths , visited ) NEW_LINE path = path [ : - 1 ] NEW_LINE DEDENT if ( isSafe ( row - 1 , col , m , n , visited ) ) : NEW_LINE INDENT path += ' U ' NEW_LINE printPathUtil ( row - 1 , col , m , n , path , possiblePaths , visited ) NEW_LINE path = path [ : - 1 ] NEW_LINE DEDENT visited [ row ] [ col ] = False NEW_LINE DEDENT def printPath ( m : List [ List [ int ] ] , n : int ) -> None : NEW_LINE INDENT possiblePaths = [ ] NEW_LINE path = " " NEW_LINE visited = [ [ False for _ in range ( MAX ) ] for _ in range ( n ) ] NEW_LINE printPathUtil ( 0 , 0 , m , n , path , possiblePaths , visited ) NEW_LINE for i in range ( len ( possiblePaths ) ) : NEW_LINE INDENT print ( possiblePaths [ i ] , end = " ▁ " ) NEW_LINE DEDENT DEDENT if __name__ == " _ _ main _ _ " : NEW_LINE INDENT m = [ [ 1 , 0 , 0 , 0 , 0 ] , [ 1 , 1 , 1 , 1 , 1 ] , [ 1 , 1 , 1 , 0 , 1 ] , [ 0 , 0 , 0 , 0 , 1 ] , [ 0 , 0 , 0 , 0 , 1 ] ] NEW_LINE n = len ( m ) NEW_LINE printPath ( m , n ) NEW_LINE DEDENT