Rat Maze Solver

Problem Description

You are given a square maze represented by a 2D matrix where each cell can be either open (1) or blocked (0). Your task is to find all possible paths from the top-left corner (starting point) to the bottom-right corner (destination) using backtracking. You can move in four directions: up (U), down (D), left (L), and right (R). You cannot visit a cell more than once in the same path.

Details

• Input: A 2D list (or array) maze of integers (either 0 or 1). The starting position is maze[0][0] and the destination is maze[n-1][n-1] where n is the number of rows. It is guaranteed that the starting cell is 1 (open).
• Output: A list (or array) of strings where each string represents a valid path from the start to the destination using characters 'U', 'D', 'L', and 'R'. If no path exists, return an empty list.

Example

For the following maze:

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

One possible output is:

["DDRDRR", "DRDDRR"]

(Note: The exact order of the paths may vary.)

Hints

• Use backtracking to explore each possible move from the current location.
• Make sure to mark cells as visited to avoid cycles, and unmark them (backtrack) when retreating.
• Consider boundary conditions and ensure you do not access cells outside the maze boundaries.

Happy coding!