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

Rat in a Maze Problem - I | Practice

Easy GraphBFSDFS GeeksforGeeks

Given an N×N maze with 0s and 1s (1 = open), find all paths from (0,0) to (N-1,N-1). You can move D, L, R, U.

Example: maze = [[1,0,0,0],[1,1,0,1],[1,1,0,0],[0,1,1,1]] → paths like "DRDDRR"

Sample Input
—
Sample Output
—
Constraints
  • 2 <= N <= 5
  • 0 <= maze[i][j] <= 1
Topics
GraphBFSDFS

Backtracking

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