Maze Path Finder

Maze Path Finder

On this day, as we celebrate progress and perseverance (and perhaps even pause to appreciate the dedication of caregivers on International Nurses Day), challenge yourself to navigate through a maze using backtracking.

Problem Description

You are given a 2D grid (maze) represented by a matrix of integers where:

• 1 represents a free cell where you can walk,
• 0 represents an obstacle.

Your task is to find all possible paths from the top-left corner (starting point) to the bottom-right corner (destination) of the maze. You may only move in four directions: Up (U), Down (D), Left (L), and Right (R).

Constraints

• You cannot move outside the boundary of the maze.
• You cannot visit the same cell more than once in a single path.
• If no path exists, return an empty list.

Input/Output

• Input: A 2D list (matrix) of integers.
• Output: A list of strings. Each string represents a valid path from start to finish, where the characters 'U', 'D', 'L', 'R' correspond to moves Up, Down, Left, and Right respectively.

Starter Code Instructions

Below is some starter code in several languages. Use the provided function signature to begin your backtracking solution. The function should return all valid paths as described.

Happy coding and enjoy solving the maze!