Rat in a Maze Problem 1 — Day 30(Python)

Photo by Mitchell Luo on Unsplash

Today, I worked on an interesting problem and thought it would be a good idea to write about it. It is a variation of the rat in a maze problem. Let us look into the question. The problem statement is from the GeeksforGeeks website.

Rat in a Maze Problem — I

Consider a rat placed at (0, 0) in a square matrix m[ ][ ] of order n and has to reach the destination at (n-1, n-1). The task is to find a sorted array of strings denoting all the possible directions which the rat can take to reach the destination at (n-1, n-1). The directions in which the rat can move are ‘U’(up), ‘D’(down), ‘L’ (left), ‘R’ (right).

Examples:

Input : N = 4
1 0 0 0
1 1 0 1
0 1 0 0
0 1 1 1
Output :
DRDDRR

Rat in Maze

Input :N = 4
1 0 0 0
1 1 0 1
1 1 0 0
0 1 1 1
Output :
DDRDRR DRDDRR
Explanation:

Rat in Maze

The problem statement requires us to find all path that helps rat reach its destination, which is one of the good indicators that we might have to use Depth-First-Search(DFS). DFS algorithms are usually implemented recursively.

The maze is represented in the form of a 2D matrix. The cell is accessed using row and column. The cell with the value 1 would mean there is a path present while 0 signifies a blocked path. The problem statement states that the rat starts at (0,0). Hence we will start from (0,0).

1. Check if the start position is marked as 1. If yes, continue with the algorithm by calling the function which has the DFS algorithm. Else, return an empty list.
2. We next need to check if the current position is our destination. If yes, append the path to the output list and return the output list.
3. We need to identify our neighbors. How would we do that? If we look at the below image, we can see how we can move by incrementing/decrementing the row/column value. Since we are allowed to move in 4 directions only, we can increment/decrement the values by 1.

Possible paths to move

4. After identifying the neighbors, we need to identify whether moving to all the neighboring spot is safe. Being safe would mean that the current row and column are well within the boundary of the maze and has a path. If it is safe recursively call the DFS function with the new position.

5. Whenever we make a move, ensure to add the move to the path. The path is a list that contains all the moves we have made to reach the current position. Change the cell value to anything other than 0,1. In the below code the cell value is changed to -1. This ensures we avoid moving in cycles.

6. Since we need to find all the paths to the destination, once we find a path change the cell value of the current position back to 1 and remove the last move from the path. This case is to be handled when the call is returned during the recursion.

7. We want the result to be in a specific format. Hence while declaring the neighbors, the following format is followed. We need the output to be in ascending order too. Hence while declaring the valid neighbors, we start with “D” then move to “L”, “R”, and “U”. We can avoid the need to sort it later.

valid_neighbour = [(1, 0, “D”),(0,-1, “L”),(0, 1, “R”), (-1, 0, “U”)]

The following code snippet is the algorithm to be followed to solve the given problem.

class PathFinder:
    def isSafe(self, row, col, n, arr):
        return(0<=row<n and 0<=col<n and arr[row][col] == 1)
    def dfs(self, curr_row, curr_col, arr, output, path, n):
        if curr_row == n-1 and curr_col == n-1:
            output.append(path)
            return output
        valid_neighbour = [(1, 0, "D"),(0,-1, "L"),(0, 1, "R"), (-1, 0, "U")]
        for n_r, n_c, d in (valid_neighbour):
            if self.isSafe(curr_row+n_r, curr_col+n_c, n, arr):
                path += d
                arr[curr_row+n_r][curr_col+n_c] = -1
                output = self.dfs(curr_row+n_r, curr_col+n_c, arr, output, path, n)
                arr[curr_row+n_r][curr_col+n_c] = 1
                path = path[:-1]
         return output
    def findPath(self,arr, n):
         start_row = 0
         start_col = 0
         if arr[start_row][start_col] == 1:
            arr[start_row][start_col] = -1
            return(self.dfs(0, 0, arr, [], "", n))
         else:
            return []

Complexity analysis.

Time Complexity

We are visiting all the cells in our maze, which takes O(N²). At any point, we have 3 options to choose from our list of neighbors. Hence the time complexity is O(3*N²).

Space Complexity

We are recursively calling the DFS function, which means internally we have a stack that keeps track of the result. Hence the space complexity is the same as the time complexity i.e. O(3*N²)

I would love to hear your feedback about my posts. Do let me know if you have any comments or feedback.