Rat in a Maze

34
0

Problem Statement

Given an n x n binary matrix maze, a rat starts at cell (0, 0) and must reach cell (n - 1, n - 1).

A cell with value 1 is open, and a cell with value 0 is blocked. Return all possible path strings using moves D, L, R, and U. A cell cannot appear more than once in a single path. If no path exists, return an empty list.

Rat in a maze

Rat in a maze

Example 1

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

Output: ["DDRDRR", "DRDDRR"]

Explanation: Both path strings start from the top-left cell and reach the bottom-right cell through open cells only.

Example 2

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

Output: []

Explanation: The destination cell is blocked, so no valid path exists.

Approach

This approach explores every valid path from the top-left cell to the bottom-right cell. At each step, it tries the directions D, L, R, U in order, while a visited matrix prevents revisiting cells in the same path. After exploring a move, the cell is unmarked so it can be used in other possible paths.

Algorithm

  • Initialize an empty answer list and a visited matrix, then return an empty list if the starting or destination cell is blocked.

  • Mark the starting cell (0, 0) as visited and start the recursive traversal with an empty path.

  • If the current cell reaches the destination (n-1, n-1), add the current path to answer and return.

  • Explore the four directions in the order D, L, R, U using direction arrays.

  • Move only to a cell that is inside the grid, open, and not visited; mark it visited, append the direction, and recurse.

  • Backtrack after recursion by removing the last direction and unmarking the cell, then return answer after all possible paths have been explored.

Dry Run

Rat

Rat

Solution

#include <bits/stdc++.h>
using namespace std;
class Solution {
private:
vector<char> direction = {'D', 'L', 'R', 'U'};
vector<int> deltaRow = {1, 0, 0, -1};
vector<int> deltaCol = {0, -1, 1, 0};
// Check whether the cell can be used in the current path.
bool canMove(int row, int col, vector<vector<int>>& maze,
vector<vector<int>>& visited, int n) {
return row >= 0 && row < n &&
col >= 0 && col < n &&
maze[row][col] == 1 &&
visited[row][col] == 0;
}
// Explore all valid paths from the current cell.
void backtrack(int row, int col, vector<vector<int>>& maze,
vector<vector<int>>& visited, string& path,
vector<string>& answer) {
int n = maze.size();
// Store the path after reaching the destination.
if (row == n - 1 && col == n - 1) {
answer.push_back(path);
return;
}
// Try moves in D, L, R, U order.
for (int move = 0; move < 4; move++) {
int nextRow = row + deltaRow[move];
int nextCol = col + deltaCol[move];
// Continue only when the next cell is valid.
if (canMove(nextRow, nextCol, maze, visited, n)) {
visited[nextRow][nextCol] = 1;
path.push_back(direction[move]);
backtrack(nextRow, nextCol, maze, visited, path, answer);
path.pop_back();
visited[nextRow][nextCol] = 0;
}
}
}
public:
// Return all valid paths from top-left to bottom-right.
vector<string> findPath(vector<vector<int>>& maze) {
int n = maze.size();
vector<string> answer;
// No path exists when the maze or endpoints are blocked.
if (n == 0 || maze[0][0] == 0 || maze[n - 1][n - 1] == 0) {
return answer;
}
vector<vector<int>> visited(n, vector<int>(n, 0));
string path;
visited[0][0] = 1;
backtrack(0, 0, maze, visited, path, answer);
return answer;
}
};
// Driver code
int main() {
vector<vector<int>> maze = {
{1, 0, 0, 0},
{1, 1, 0, 1},
{1, 1, 0, 0},
{0, 1, 1, 1}
};
// instance for class Solution
Solution sol;
vector<string> answer = sol.findPath(maze);
for (string pathValue : answer) {
cout << pathValue << " ";
}
return 0;
}

Complexity Analysis

Here, N is the size of the maze, so the grid has N² cells. Let P be the number of returned paths.

Time Complexity: O(4^(N²)), because the search can branch in up to four directions over a path of at most N² cells.

Auxiliary Space Complexity: O(N²), because the visited matrix, recursion stack, and current path can grow with the number of cells.

Output Space Complexity: O(P × N²), because there can be P returned paths and each path string has at most N² - 1 moves.

Interview follow-up Questions

No. Repeating a cell can create cycles, so visited marking blocks repeated cells inside a single path.

RecursionTCS NQT

Read Similar Blogs

Comments0