Find All Paths in a Maze

You are given a 2D grid representing a maze where:

• 'S' represents the starting point,

• 'E' represents the ending point,

• '0' represents open paths, and

• '1' represents walls.

You need to find all possible paths from 'S' to 'E' using backtracking. You can move up, down, left, or right, but you cannot move through walls.

Example

Input:

const maze = [
  ['S', '0', '1', '0'],
  ['0', '1', '0', '0'],
  ['0', '0', '0', '1'],
  ['0', '1', 'E', '0']
];

Output:

[
  [[0, 0], [1, 0], [2, 0], [2, 1], [2, 2], [3, 2]]
]

This output represents the path from 'S' to 'E' as a list of coordinates.

Function Declaration:

function findPathsInMaze(maze) {
  // Your implementation goes here
}

---

Great! Let's break down the approach to solve this problem using backtracking.

Step 2: Short, Easy-to-Remember Solution/Approach

1. Identify the starting point ('S') in the maze.

2. Use a backtracking function to explore all possible paths:

   • Move in all four possible directions (up, down, left, right).

   • Keep track of the current path.

   • If you reach the endpoint ('E'), save the path.

   • Mark cells as visited to avoid cycles and unmark them when backtracking.

3. Return all found paths.

Step 3: Solution in JavaScript with Code Commenting

Here's the complete code with comments explaining each step:

function findPathsInMaze(maze) {
  const rows = maze.length;
  const cols = maze[0].length;
  const paths = [];

  // Helper function for backtracking
  function backtrack(row, col, path) {
    // Base case: if out of bounds or hits a wall
    if (row < 0 || col < 0 || row >= rows || col >= cols || maze[row][col] === '1') {
      return;
    }

    // Base case: if the endpoint is reached
    if (maze[row][col] === 'E') {
      path.push([row, col]);
      paths.push([...path]);
      path.pop();
      return;
    }

    // Mark the cell as part of the path
    const temp = maze[row][col];
    maze[row][col] = '1';  // Mark as visited
    path.push([row, col]);

    // Explore the four possible directions
    backtrack(row + 1, col, path); // Move down
    backtrack(row - 1, col, path); // Move up
    backtrack(row, col + 1, path); // Move right
    backtrack(row, col - 1, path); // Move left

    // Unmark the cell (backtrack step)
    maze[row][col] = temp;
    path.pop();
  }

  // Start backtracking from the starting point
  for (let i = 0; i < rows; i++) {
    for (let j = 0; j < cols; j++) {
      if (maze[i][j] === 'S') {
        backtrack(i, j, []);
        break;
      }
    }
  }

  return paths;
}

// Example usage:
const maze = [
  ['S', '0', '1', '0'],
  ['0', '1', '0', '0'],
  ['0', '0', '0', '1'],
  ['0', '1', 'E', '0']
];

console.log(findPathsInMaze(maze));

Step 4: Explanation of the Solution in Simple Terms

Explanation for a 10-year-old: Imagine you are in a garden maze. You start at a special flower (S) and want to find all possible ways to reach the magical tree (E). You can only walk on grass (0) and cannot go through bushes (1). You decide to try every possible path, marking where you have walked so you don't go in circles, and once you find the magical tree, you remember that path. After trying every way, you tell all the paths you found.

Step 5: Code Explanation in Pointers

1. Identify the starting point: Loop through the maze to find 'S'.

2. Backtrack function: Define a helper function to explore paths.

   • Base cases: Return if out of bounds, hit a wall, or reach 'E'.

   • Mark cell as visited: Temporarily mark the cell to avoid revisiting.

   • Explore directions: Recursively explore up, down, left, and right.

   • Unmark cell: Backtrack by unmarking the cell.

3. Start backtracking: Call the backtracking function from the starting point.

4. Return paths: Collect and return all valid paths.

Step 6: Complexity Analysis

• Time Complexity: O(4^(n*m)), where n is the number of rows and m is the number of columns. This is because, in the worst case, every cell could lead to four recursive calls.

• Space Complexity: O(n*m), due to the recursion stack and path storage.

---