Rat in a Maze

Real-life Problem Solving

Imagine being in a maze with walls and open paths, starting at the top-left corner and needing to reach the bottom-right corner. The task involves finding all possible paths from the start to the destination. Each step taken must be carefully considered to avoid walls and ensure a valid route to the end. If a path is blocked, the process involves backtracking and trying another direction, keeping track of each step to ensure no part of the maze is visited twice unnecessarily.

Intuition Behind Recursion Process

This maze-solving process can be translated into a recursive function. The starting position in the maze is equivalent to the initial call of the recursive function. Each possible direction (up, down, left, right) corresponds to a recursive call exploring that direction. Upon finding a valid move (an open path), the current path is updated and the function proceeds to the next step. When a dead end is encountered (a blocked path), the function backtracks to the previous step and explores alternative directions. This recursive exploration continues until the destination is reached, recording all possible paths.

Approach

Start from the initial position (0,0) in the grid.
Check if the current position is the destination. If so, add the current path to the results.
If the current cell is blocked (value is 0), return.
Mark the current cell as visited by setting its value to 0.
Explore all possible directions (up, down, left, right) from the current cell:

Move up if the current cell is not in the topmost row.
Move left if the current cell is not in the leftmost column.
Move down if the current cell is not in the bottommost row.
Move right if the current cell is not in the rightmost column.

After exploring all directions, unmark the current cell by resetting its value to 1 to allow other paths to pass through it.
Repeat the above steps recursively until all possible paths are explored.
Sort the resulting paths alphabetically.

Dry Run

Solution

#include<bits/stdc++.h>
using namespace std;

// Vector to mark visited cells
vector<vector<int>> visited(5, vector<int>(5, 0));

// Vector to store the resulting paths
vector<string> result;

class Solution {
public:
    // Recursive function to find paths
    void path(vector<vector<int>>& m, int x, int y, string dir, int n) {
        // If destination is reached, add path to result
        if (x == n - 1 && y == n - 1) {
            result.push_back(dir);
            return;
        }

        // If cell is blocked, return
        if (m[x][y] == 0) return;

        // Mark cell as visited by setting it to 0
        m[x][y] = 0;

        // Move up if possible
        if (x > 0) path(m, x - 1, y, dir + 'U', n);
        // Move left if possible
        if (y > 0) path(m, x, y - 1, dir + 'L', n);
        // Move down if possible
        if (x < n - 1) path(m, x + 1, y, dir + 'D', n);
        // Move right if possible
        if (y < n - 1) path(m, x, y + 1, dir + 'R', n);

        // Unmark cell as visited by setting it to 1
        m[x][y] = 1;
    }

    // Function to find all paths
    vector<string> findPath(vector<vector<int>>& grid) {
        int n = grid.size();
       
        // Clear previous results
        result.clear();

        // If starting or ending cell is blocked, return empty result
        if (grid[0][0] == 0 || grid[n - 1][n - 1] == 0) return result;

        // Start finding paths from (0, 0)
        path(grid, 0, 0, "", n);

        // Sort the result paths
        sort(result.begin(), result.end());

        return result;
    }
};

int main() {
    // Define the grid
    vector<vector<int>> grid = {
        {1, 0, 0, 0, 0},
        {1, 1, 0, 1, 1},
        {0, 1, 0, 0, 1},
        {0, 1, 1, 1, 1},
        {0, 0, 0, 0, 1}
    };

    // Create an instance of the Solution class
    Solution sol;

    // Find all paths in the grid
    vector<string> paths = sol.findPath(grid);

    // Print all the found paths
    for (const string& path : paths) {
        cout << path << endl;
    }

    return 0;
}
import java.util.*;

class Solution {
    // List to store the resulting paths
    List<String> result = new ArrayList<>();

    // Recursive function to find paths
    private void path(int[][] m, int x, int y, String dir, int n) {
        // If destination is reached, add path to result
        if (x == n - 1 && y == n - 1) {
            result.add(dir);
            return;
        }

        // If cell is blocked, return
        if (m[x][y] == 0) return;

        // Mark cell as visited by setting it to 0
        m[x][y] = 0;

        // Move up if possible
        if (x > 0) path(m, x - 1, y, dir + 'U', n);
        // Move left if possible
        if (y > 0) path(m, x, y - 1, dir + 'L', n);
        // Move down if possible
        if (x < n - 1) path(m, x + 1, y, dir + 'D', n);
        // Move right if possible
        if (y < n - 1) path(m, x, y + 1, dir + 'R', n);

        // Unmark cell as visited by setting it to 1
        m[x][y] = 1;
    }

    public List<String> findPath(int[][] grid) {
        int n = grid.length;

        // Clear previous results
        result.clear();

        // If starting or ending cell is blocked, return empty result
        if (grid[0][0] == 0 || grid[n - 1][n - 1] == 0) return result;

        // Start finding paths from (0, 0)
        path(grid, 0, 0, "", n);

        // Sort the result paths
        Collections.sort(result);

        return result;
    }

    public static void main(String[] args) {
        Solution sol = new Solution();
        int[][] grid = {
            {1, 0, 0, 0, 0},
            {1, 1, 0, 1, 1},
            {0, 1, 0, 0, 1},
            {0, 1, 1, 1, 1},
            {0, 0, 0, 0, 1}
        };

        List<String> paths = sol.findPath(grid);

        for (String path : paths) {
            System.out.println(path);
        }
    }
}
class Solution:
    def __init__(self):
        self.result = []

    # Recursive function to find paths
    def path(self, m, x, y, dir, n):
        # If destination is reached, add path to result
        if x == n - 1 and y == n - 1:
            self.result.append(dir)
            return

        # If cell is blocked, return
        if m[x][y] == 0:
            return

        # Mark cell as visited by setting it to 0
        m[x][y] = 0

        # Move up if possible
        if x > 0:
            self.path(m, x - 1, y, dir + 'U', n)
        # Move left if possible
        if y > 0:
            self.path(m, x, y - 1, dir + 'L', n)
        # Move down if possible
        if x < n - 1:
            self.path(m, x + 1, y, dir + 'D', n)
        # Move right if possible
        if y < n - 1:
            self.path(m, x, y + 1, dir + 'R', n)

        # Unmark cell as visited by setting it to 1
        m[x][y] = 1

    def findPath(self, grid):
        n = len(grid)
        self.result = []

        # If starting or ending cell is blocked, return empty result
        if grid[0][0] == 0 or grid[n - 1][n - 1] == 0:
            return self.result

        # Start finding paths from (0, 0)
        self.path(grid, 0, 0, "", n)

        # Sort the result paths
        self.result.sort()

        return self.result

# Example usage
if __name__ == "__main__":
    sol = Solution()
    grid = [
        [1, 0, 0, 0, 0],
        [1, 1, 0, 1, 1],
        [0, 1, 0, 0, 1],
        [0, 1, 1, 1, 1],
        [0, 0, 0, 0, 1]
    ]

    paths = sol.findPath(grid)

    for path in paths:
        print(path)
class Solution {
    constructor() {
        this.result = [];
    }

    // Recursive function to find paths
    path(m, x, y, dir, n) {
        // If destination is reached, add path to result
        if (x === n - 1 && y === n - 1) {
            this.result.push(dir);
            return;
        }

        // If cell is blocked, return
        if (m[x][y] === 0) return;

        // Mark cell as visited by setting it to 0
        m[x][y] = 0;

        // Move up if possible
        if (x > 0) this.path(m, x - 1, y, dir + 'U', n);
        // Move left if possible
        if (y > 0) this.path(m, x, y - 1, dir + 'L', n);
        // Move down if possible
        if (x < n - 1) this.path(m, x + 1, y, dir + 'D', n);
        // Move right if possible
        if (y < n - 1) this.path(m, x, y + 1, dir + 'R', n);

        // Unmark cell as visited by setting it to 1
        m[x][y] = 1;
    }

    findPath(grid) {
        const n = grid.length;
        this.result = [];

        // If starting or ending cell is blocked, return empty result
        if (grid[0][0] === 0 || grid[n - 1][n - 1] === 0) return this.result;

        // Start finding paths from (0, 0)
        this.path(grid, 0, 0, "", n);

        // Sort the result paths
        this.result.sort();

        return this.result;
    }
}

// Example usage
const sol = new Solution();
const grid = [
    [1, 0, 0, 0, 0],
    [1, 1, 0, 1, 1],
    [0, 1, 0, 0, 1],
    [0, 1, 1, 1, 1],
    [0, 0, 0, 0, 1]
];

const paths = sol.findPath(grid);

for (const path of paths) {
    console.log(path);
}

Complexity Analysis

Time Complexity : The time complexity is O(4^(N^2)) due to recursion exploring all paths in the grid.

Space Complexity :The space complexity is O(N^2) for the recursion stack and result storage.

Problem List

Examples:

Constraints

Hints

Company Tags

Editorial

Real-life Problem Solving

Intuition Behind Recursion Process

Approach

Dry Run

Solution

Complexity Analysis

Frequently Occurring Doubts

Interview Followup Questions

Notes

Code