Unique Maze Paths

Backtracking Maze Pathfinding Algorithm

Unique Maze Paths

On March 23rd, when many celebrate creative puzzles and problem solving, try your hand at navigating a maze using backtracking! In this problem you are given a 2D maze represented as a grid. Each cell in the maze is either free (represented by 0) or blocked (represented by 1).

Objective:

Write a function findPaths which returns all possible paths from the top-left corner of the maze to the bottom-right corner. You can move in four directions: Up (U), Down (D), Left (L), and Right (R). A valid move must stay within the bounds of the maze, cannot enter a blocked cell, and should not revisit cells in the same path.

Input:

A 2D grid (array) where free cells are denoted by 0 and blocked cells by 1.

Output:

An array (or list) of strings. Each string represents a valid path from the start to finish using the characters U, D, L, and R.

Example:

For the maze below:

maze = [
  [0, 0, 0],
  [1, 0, 1],
  [0, 0, 0]
]

A possible output could be:

["DDRDRR", "DRDDRR", ...]

Hint:

Utilize backtracking to explore all possible routes. Mark cells as visited before moving on, and backtrack (i.e., unmark them) when a path does not lead to the destination.