Rat in a Maze Problem – I

Consider a rat placed at (0, 0) in a square matrix mat of order n* n. It has to reach the destination at (n – 1, n – 1). Find all possible paths that the rat can take to reach from source to destination. The directions in which the rat can move are ‘U'(up), ‘D'(down), ‘L’ (left), ‘R’ (right). Value 0 at a cell in the matrix represents that it is blocked and rat cannot move to it while value 1 at a cell in the matrix represents that rat can be travel through it.
Note: In a path, no cell can be visited more than one time. If the source cell is 0, the rat cannot move to any other cell. In case of no path, return an empty list. The driver will output “-1” automatically.

Examples:

Input: mat[][] = [[1, 0, 0, 0],
                [1, 1, 0, 1], 
                [1, 1, 0, 0],
                [0, 1, 1, 1]]
Output: DDRDRR DRDDRR
Explanation: The rat can reach the destination at (3, 3) from (0, 0) by two paths - DRDDRR and DDRDRR, when printed in sorted order we get DDRDRR DRDDRR.

Input: mat[][] = [[1, 0],
                [1, 0]]
Output: -1
Explanation: No path exists and destination cell is blocked.

Expected Time Complexity: O(3^{n^2})
Expected Auxiliary Space: O(l * x)
Here l = length of the path, x = number of paths.

Constraints:
2 ≤ n ≤ 5
0 ≤ mat[i][j] ≤ 1

Approach 01:

#include <vector>
#include <string>

using namespace std;

class Solution {
public:
    vector<string> findPath(vector<vector<int>>& maze) {
        // Check if the start or end point is blocked
        if (maze.empty() || maze[0].empty() || maze[0][0] == 0 || maze.back().back() == 0) {
            return {};
        }

        int numRows = maze.size();
        int numCols = maze[0].size();
        vector<string> allPaths;

        searchPaths(maze, 0, 0, numRows, numCols, "", allPaths);
        return allPaths;
    }

private:
    void searchPaths(vector<vector<int>>& maze, int row, int col, int numRows, int numCols, string currentPath, vector<string>& allPaths) {
        // If the bottom-right corner is reached, add the current path to the paths list
        if (row == numRows - 1 && col == numCols - 1) {
            allPaths.push_back(currentPath);
            return;
        }

        // Mark the current cell as visited
        maze[row][col] = 0;

        // Define the possible directions: Up, Right, Down, Left
        vector<pair<pair<int, int>, char>> directions = {
            {{-1, 0}, 'U'}, {{0, 1}, 'R'}, {{1, 0}, 'D'}, {{0, -1}, 'L'}
        };

        for (const auto& direction : directions) {
            int newRow = row + direction.first.first;
            int newCol = col + direction.first.second;
            // Check if the new position is within bounds and not visited
            if (newRow >= 0 && newRow < numRows && newCol >= 0 && newCol < numCols && maze[newRow][newCol] == 1) {
                searchPaths(maze, newRow, newCol, numRows, numCols, currentPath + direction.second, allPaths);
            }
        }

        // Mark the current cell as unvisited for other paths
        maze[row][col] = 1;
    }
};

from typing import List

class Solution:
    def findPath(self, maze: List[List[int]]) -> List[str]:
        # Check if the start or end point is blocked
        if not maze[0][0] or not maze[-1][-1]:
            return []

        numRows, numCols = len(maze), len(maze[0])
        allPaths = []

        def searchPaths(maze, row, col, numRows, numCols, currentPath):
            # If the bottom-right corner is reached, add the current path to the paths list
            if row == numRows - 1 and col == numCols - 1:
                allPaths.append(currentPath)
                return

            # Mark the current cell as visited
            maze[row][col] = 0

            # Define the possible directions: Up, Right, Down, Left
            directions = [(-1, 0, "U"), (0, 1, "R"), (1, 0, "D"), (0, -1, "L")]

            for dRow, dCol, direction in directions:
                newRow, newCol = row + dRow, col + dCol
                # Check if the new position is within bounds and not visited
                if 0 <= newRow < numRows and 0 <= newCol < numCols and maze[newRow][newCol] == 1:
                    searchPaths(maze, newRow, newCol, numRows, numCols, currentPath + direction)

            # Mark the current cell as unvisited for other paths
            maze[row][col] = 1

        searchPaths(maze, 0, 0, numRows, numCols, "")
        return allPaths

Time Complexity

• Initialization:

  Checking if the start or end point is blocked takes \( O(1) \) time.

• Recursive Search:

  The function searchPaths explores all possible paths in the maze, where each cell can be visited multiple times. The worst-case time complexity is exponential, \( O(4^{(n \times m)}) \), where \( n \) is the number of rows and \( m \) is the number of columns.

• Overall Time Complexity:

  The overall time complexity is \( O(4^{(n \times m)}) \).

Space Complexity

• Space for Variables:

  The space used by variables numRows, numCols, and directions is \( O(1) \).

• Recursive Call Stack:

  The maximum depth of the recursive call stack can be \( O(n \times m) \) in the worst case.

• Storage for Paths:

  In the worst case, if all possible paths are valid, the space required to store them is \( O(4^{(n \times m)}) \).

• Overall Space Complexity:

  The overall space complexity is \( O(4^{(n \times m)}) \).