Rat in a Maze Solution

code:

 def pathUtil(maze,visited,sol,x,y,N,possible):

    #print(sol)

    if x<0 or y<0 or x>N-1 or y>N-1 or maze[x][y]==0 or visited[x][y]==1:

        return

    

    if x==N-1 and y==N-1 and maze[x][y]==1:

        possible.append(sol)

        return

    

    visited[x][y]=1

    

    pathUtil(maze,visited,sol+'D',x+1,y,N,possible)

    pathUtil(maze,visited,sol+'U',x-1,y,N,possible)

    pathUtil(maze,visited,sol+'R',x,y+1,N,possible)

    pathUtil(maze,visited,sol+'L',x,y-1,N,possible)

    

    visited[x][y]=0

    

def path(maze,N):

    visited=[[0 for i in range(N)] for j in range(N)]

    sol=''

    possible=[]

    pathUtil(maze,visited,sol,0,0,N,possible)

    

    print("possible path : ",possible)

    

N = 4

maze = [[1, 0, 0, 0],

         [1, 1, 0, 1], 

         [1, 1, 0, 0],

         [0, 1, 1, 1]]

         

path(maze,N)