Rat In A Maze | Backtracking | Intuitive + Short CPP Code | Self Explanatory Comments
vHiren
18412
BacktrackingInterview

Suppose a rat placed at cell (0, 0) in a square matrix 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.

Input: N = 4
{{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.

Note: Hey There! Just Take A Look At The Code And Comments Within It. You'll Get It.
Note: Time Complexity And Auxiliary Space Is Mentioned With The Code.
Note: If You Have Any Kind Of Doubt, Just Comment And I'll Be There For You.

Suggestion (Watch If You Have Solved The Above One) : https://leetcode.com/problems/path-with-maximum-gold/solutions/5164674/backtracking-one-only-readable-solution-best-explanation-using-comments/

class Backtracking {
    vector<vector<int>> directions = {{-1, 0, 'U'}, {1, 0, 'D'}, {0, -1, 'L'}, {0, 1, 'R'}};
    vector<string> allPaths;
    string currentPath;       
  
    void generateAllDestPaths(vector<vector<int>>& grid, int N, int R, int C) {
        // Edge case: If at any point you walk outside of the grid or walk into the cell through which you can't go through then return
        if(R < 0 || C < 0 || R == N || C == N || grid[R][C] == 0)
            return;
            
        // Edge case: If reached the destination cell then store the current path to the result array 
        if(R == N-1 && C == N-1) {
            allPaths.push_back(currentPath);
            return;
        }

        // Mark as visited
        grid[R][C] = 0;  

        // Explore all 4 directions one by one from cell (R, C)
        for(auto& dir : directions) {
            int reachRow  = dir[0];
            int reachCol  = dir[1];
            char letter   = dir[2];
            currentPath.push_back(letter); // Include the direction
            generateAllDestPaths(grid, N, R + reachRow, C + reachCol); 
            currentPath.pop_back();  // Exclude the direction
        }

        // Mark as unvisited
        grid[R][C] = 1; 
    }
    
public:
    // Method to find all the possible paths that the rat can take to reach the destination - O(4^(N*N) * M) & O(N*N) : Where M let be the maximum possible size of string `currentPath`
    vector<string> findPath(vector<vector<int>>& grid, int N) {
        generateAllDestPaths(grid, N, 0, 0);
        return allPaths;
    }
};

𝗨𝗣𝗩𝗢𝗧𝗘 𝗜𝗙 𝗬𝗢𝗨 𝗟𝗜𝗞𝗘 𝗧𝗛𝗘 𝗦𝗢𝗟𝗨𝗧𝗜𝗢𝗡 👍

Note: This solution is created by myself :)

Comments (10)