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
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
answerlist and avisitedmatrix, 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 toanswerand return.Explore the four directions in the order
D, L, R, Uusing 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
answerafter all possible paths have been explored.
Dry Run
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 codeint 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.
Be the first to add a comment.