Find all possible paths for a Rat to move in a Maze

Given a maze represented by a 2D grid (matrix), find all possible paths for a rat to move from the top-left corner to the bottom-right corner. The rat can only move in four directions: up (U), down (D), left (L), and right (R). The maze contains walls (represented as 0), which the rat cannot pass through, and open paths (represented as 1), which the rat can move through.

Input/Output Examples

plaintext
Example 1:
Input:
maze = [
    [1, 0, 0, 0],
    [1, 1, 0, 1],
    [0, 1, 0, 0],
    [1, 1, 1, 1]]

Output: ["DRDDRR", "DDRDRR"]
Explanation: The valid paths for the rat are "DRDDRR" and "DDRDRR".

Example 2:
Input:
maze = [
    [1, 0],
    [0, 1]
]

Output: []
Explanation: There is no possible path from the top-left to the bottom-right.

Approach to Solve the Rat in a Maze Problem

  1. Recursive Backtracking:
    • Start at the top-left corner of the maze (0, 0) and attempt to move in all four possible directions: up, down, left, and right.
    • For each move, check if it is valid (i.e., within the maze boundaries and on a path (1)).
  2. Mark Visited Cells:
    • To avoid infinite loops, mark the cells you have already visited. Backtrack and unmark the cell if the current path does not lead to the solution.
  3. Store and Return Valid Paths:
    • Once the rat reaches the bottom-right corner, store the current path. Continue exploring other possible paths using backtracking until all options are exhausted.
  4. Return Paths:
    • Return all valid paths that lead from the start to the destination.

C++ Program to Solve the Rat in a Maze Problem

cpp
#include <iostream>
#include <vector>
#include <string>
using namespace std;

bool isValid(int x, int y, const vector<vector<int>>& maze, vector<vector<bool>>& visited) {
    int n = maze.size();
    return (x >= 0 && x < n && y >= 0 && y < n && maze[x][y] == 1 && !visited[x][y]);
}

void findPaths(vector<vector<int>>& maze, int x, int y, vector<vector<bool>>& visited, string path, vector<string>& result) {
    int n = maze.size();
    if (x == n - 1 && y == n - 1) {
        result.push_back(path);
        return;
    }

    // Mark this cell as visited
    visited[x][y] = true;

    // Move Down
    if (isValid(x + 1, y, maze, visited)) {
        findPaths(maze, x + 1, y, visited, path + 'D', result);
    }

    // Move Right
    if (isValid(x, y + 1, maze, visited)) {
        findPaths(maze, x, y + 1, visited, path + 'R', result);
    }

    // Move Up
    if (isValid(x - 1, y, maze, visited)) {
        findPaths(maze, x - 1, y, visited, path + 'U', result);
    }

    // Move Left
    if (isValid(x, y - 1, maze, visited)) {
        findPaths(maze, x, y - 1, visited, path + 'L', result);
    }

    // Backtrack: Unmark this cell as visited
    visited[x][y] = false;
}

vector<string> ratInMaze(vector<vector<int>>& maze) {
    int n = maze.size();
    vector<string> result;
    vector<vector<bool>> visited(n, vector<bool>(n, false));

    if (maze[0][0] == 1) {
        findPaths(maze, 0, 0, visited, "", result);
    }

    return result;
}

int main() {
    vector<vector<int>> maze = {
        {1, 0, 0, 0},
        {1, 1, 0, 1},
        {0, 1, 0, 0},
        {1, 1, 1, 1}
    };

    vector<string> result = ratInMaze(maze);
    if (result.empty()) {
        cout << "No solution found" << endl;
    } else {
        for (const string& path : result) {
            cout << path << endl;
        }
    }

    return 0;
}

Java Program to Solve the Rat in a Maze Problem

java
import java.util.ArrayList;
import java.util.List;

public class RatInMaze {

    private static boolean isValid(int x, int y, int[][] maze, boolean[][] visited) {
        int n = maze.length;
        return (x >= 0 && x < n && y >= 0 && y < n && maze[x][y] == 1 && !visited[x][y]);
    }

    private static void findPaths(int[][] maze, int x, int y, boolean[][] visited, String path, List<String> result) {
        int n = maze.length;
        if (x == n - 1 && y == n - 1) {
            result.add(path);
            return;
        }

        visited[x][y] = true;

        if (isValid(x + 1, y, maze, visited)) {
            findPaths(maze, x + 1, y, visited, path + 'D', result);
        }

        if (isValid(x, y + 1, maze, visited)) {
            findPaths(maze, x, y + 1, visited, path + 'R', result);
        }

        if (isValid(x - 1, y, maze, visited)) {
            findPaths(maze, x - 1, y, visited, path + 'U', result);
        }

        if (isValid(x, y - 1, maze, visited)) {
            findPaths(maze, x, y - 1, visited, path + 'L', result);
        }

        visited[x][y] = false;
    }

    public static List<String> ratInMaze(int[][] maze) {
        int n = maze.length;
        List<String> result = new ArrayList<>();
        boolean[][] visited = new boolean[n][n];

        if (maze[0][0] == 1) {
            findPaths(maze, 0, 0, visited, "", result);
        }

        return result;
    }

    public static void main(String[] args) {
        int[][] maze = {
            {1, 0, 0, 0},
            {1, 1, 0, 1},
            {0, 1, 0, 0},
            {1, 1, 1, 1}
        };

        List<String> result = ratInMaze(maze);
        if (result.isEmpty()) {
            System.out.println("No solution found");
        } else {
            for (String path : result) {
                System.out.println(path);
            }
        }
    }
}

Python Program to Solve the Rat in a Maze Problem

python
# Function to check if the move is valid
def is_valid(x, y, maze, visited):
    n = len(maze)
    return 0 <= x < n and 0 <= y < n and maze[x][y] == 1 and not visited[x][y]

# Recursive function to find all paths
def find_paths(maze, x, y, visited, path, result):
    n = len(maze)
    if x == n - 1 and y == n - 1:
        result.append(path)
        return

    visited[x][y] = True

    # Move Down
    if is_valid(x + 1, y, maze, visited):
        find_paths(maze, x + 1, y, visited, path + 'D', result)

    # Move Right
    if is_valid(x, y + 1, maze, visited):
        find_paths(maze, x, y + 1, visited, path + 'R', result)

    # Move Up
    if is_valid(x - 1, y, maze, visited):
        find_paths(maze, x - 1, y, visited, path + 'U', result)

    # Move Left
    if is_valid(x, y - 1, maze, visited):
        find_paths(maze, x, y - 1, visited, path + 'L', result)

    visited[x][y] = False

# Function to solve the rat in a maze problem
def rat_in_maze(maze):
    n = len(maze)
    result = []
    visited = [[False for _ in range(n)] for _ in range(n)]

    if maze[0][0] == 1:
        find_paths(maze, 0, 0, visited, "", result)

    return result

# Example usage
if __name__ == "__main__":
    maze = [
        [1, 0, 0, 0],
        [1, 1, 0, 1],
        [0, 1, 0, 0],
        [1, 1, 1, 1]
    ]
    result = rat_in_maze(maze)
    if not result:
        print("No solution found")
    else:
        for path in result:
            print(path)
  • Time Complexity: O(4^(n^2)) in the worst case, where n is the size of the grid. The rat can move in four directions, and all cells may need to be visited recursively.
  • Space Complexity: O(n^2) due to the recursive call stack and the visited matrix used to keep track of the cells.

DSA

3443

533

Related Articles