Rat in a Maze Problem - I | Practice Easy 0 attempts
GeeksforGeeks ↗

Rat in a Maze Problem - I | Practice

Easy GraphBFSDFS GeeksforGeeks

You're given an N×N maze made of 0s and 1s, where a 1 marks a cell you're allowed to step on. Starting at (0,0), find every path to (N-1,N-1), moving only Down, Left, Right, or Up at each step.

Do not revisit a cell within a path. Return an empty array when the source is blocked or no path reaches the destination.

Input Format
Implement findPath(maze). Inputs below show JavaScript function arguments; there is no stdin parsing.
Output Format
Return the result described in the statement. The order of the outer result array does not matter.

Sample Input and Output

Example 1 · Run Sample

Input
maze = [[1,0,0,0],[1,1,0,1],[1,1,0,0],[0,1,1,1]]
Output
["DDRDRR","DRDDRR"]

Example 2

Input
maze = [[0]]
Output
[]
Constraints
  • 1 <= maze.length <= 5
  • maze is square; maze[i][j] is 0 or 1
  • Paths cannot revisit cells.
Test Cases (2)
Case 1
Args: [[[1,0,0,0],[1,1,0,1],[1,1,0,0],[0,1,1,1]]] Expected: ["DDRDRR","DRDDRR"]
Case 2
Args: [[[0]]] Expected: []
Topics
GraphBFSDFS

Backtracking

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

Time: O(4^(n²)) | Space: O(n²)

Saved in this browser only. Private to you.

JavaScript