Maze Backtracking Paths

Maze Backtracking Paths

Today's challenge is to help navigate a maze using backtracking. Imagine a maze represented as a 2D grid where each cell has a value:

• 1: The cell is open and you can step into it.
• 0: The cell is blocked.

You start at the top-left corner of the maze (position (0,0)) and your goal is to reach the bottom-right corner (position (n-1, m-1)). Your task is to find all possible paths from the start to the goal. Each move can be in one of four directions: up, down, left, or right. You cannot revisit a cell in the same path.

For each valid path, return a string that represents the sequence of moves. For example, R for right, D for down, L for left, and U for up.

Note: Since today (April 5) is a day celebrated by puzzle enthusiasts, think of this problem as uncovering hidden paths in a maze, much like finding Easter eggs in a puzzle.

Function Signature

You should implement a function with the following signature that takes in the maze as input and returns a list (or array) of valid path strings.

findMazePaths(maze: List[List[int]]) -> List[str]

Input/Output Example

For a maze like:

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

A possible output could be:

["DDRDRR", "DRDDRR"]

Hint: Use backtracking to explore every possible way to move and ensure you do not visit the same cell twice in a path.