Rat in a maze — print all paths
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: []
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.