Rat in a maze — print all paths

Medium

Problem

A rat starts at (0, 0) of an n × n grid (1 = open, 0 = blocked) and must reach (n−1, n−1). It moves U, D, L or R and cannot revisit a cell. Return every path as a string of moves, in lexicographic order.

Example 1

Input:  [[1,0,0,0], [1,1,0,1], [1,1,0,0], [0,1,1,1]]
Output: ["DDRDRR", "DRDDRR"]

Also asked as: Rat in a maze Problem · Find shortest safe route in a path with landmines

Test cases

Case 1

Input:    [[1,0,0,0],[1,1,0,1],[1,1,0,0],[0,1,1,1]]
Expected: ["DDRDRR","DRDDRR"]

Case 2

Input:    [[1,1],[1,1]]
Expected: ["DR","RD"]

Case 3

Input:    [[1,0],[0,1]]
Expected: []

Case 4

Input:    [[0,1],[1,1]]
Expected: []

Your solution ✓ Solved

Ctrl/⌘ + Enter to run
View solutionHide solution1 approach

1. DFS with a visited mark, path string, undo on return

Time O(4^(R·C))Space O(R·C)

From (0,0) try moves D,L,R,U (order defines lexical output); mark the cell, recurse, unmark. Record the path when you reach the target.

function ratMaze(grid) {
const n = grid.length, res = [];
const vis = Array.from({ length: n }, () => Array(n).fill(false));
const dirs = [[1, 0, 'D'], [0, -1, 'L'], [0, 1, 'R'], [-1, 0, 'U']];
const bt = (r, c, path) => {
if (r === n - 1 && c === n - 1) { res.push(path); return; }
for (const [dr, dc, ch] of dirs) {
const nr = r + dr, nc = c + dc;
if (nr >= 0 && nc >= 0 && nr < n && nc < n && !vis[nr][nc] && grid[nr][nc] === 1) {
vis[nr][nc] = true;
bt(nr, nc, path + ch);
vis[nr][nc] = false;
}
}
};
if (grid[0][0] === 1) { vis[0][0] = true; bt(0, 0, ''); }
return res;
}

Shortest safe route with landmines: mark every cell adjacent to a mine as unsafe first, then either backtrack tracking the best length, or BFS for the true shortest.