Rat in a maze

Hard TimeO(4^(n²)) SpaceO(n²)

A grid maze marks open cells with 1 and walls with 0. A rat starts in the top-left corner and wants the bottom-right, moving only between neighbouring cells and never diagonally. Return a path as a list of [row, column] pairs. A blocked cell may not be entered, and the path must not revisit a cell it has already passed through.

Examples

Example 1

Input
maze = [[1, 0, 0, 0], [1, 1, 0, 1], [0, 1, 0, 0], [1, 1, 1, 1]]
Output
[[0,0],[1,0],[1,1],[2,1],[3,1],[3,2],[3,3]]
Down the left side, across to the middle column, down to the bottom row and right to the corner.

Example 2

Input
maze = [[1, 0], [0, 1]]
Output
[]
The two open cells touch only at a corner, and diagonal moves are not allowed — so no path exists.

The Code

function solveMaze(maze) {
  const n = maze.length;
  const path = [];
  function move(r, c) {
    if (r < 0 || c < 0 || r >= n || c >= n) return false;
    if (maze[r][c] !== 1) return false;
    path.push([r, c]);
    maze[r][c] = 2;
    if (r === n - 1 && c === n - 1) return true;
    if (move(r + 1, c)) return true;
    if (move(r, c + 1)) return true;
    if (move(r - 1, c)) return true;
    if (move(r, c - 1)) return true;
    path.pop();
    maze[r][c] = 1;
    return false;
  }
  move(0, 0);
  return path;
}
solveMaze([[1, 0, 0, 0], [1, 1, 0, 1], [0, 1, 0, 0], [1, 1, 1, 1]]);
Done
Step through solveMaze([[1, 0, 0, 0], [1, 1, 0, 1], [0, 1, 0, 0], [1, 1, 1, 1]]) call by call

More like this

All backtracking examples (10) →