Maze Path Finder

Problem Description:

Given a 2D grid representing a maze, write a function that finds one valid path from the top-left corner (0, 0) to the bottom-right corner (n-1, m-1) using a backtracking algorithm. The maze is represented as a 2D array (or list of lists) where a cell with a value of 1 indicates an open path and 0 indicates a blocked cell (wall).

Rules:

• You can move in four directions: up, down, left, and right. Diagonal moves are not allowed.
• Avoid revisiting cells to prevent infinite loops.
• Return the path as a list of coordinates (row, column), including both the start and end points.
• If no valid path exists, return an empty list.

Example:

For the maze below:

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

A possible valid path is:

[(0, 0), (1, 0), (1, 1), (2, 1), (3, 1), (3, 2), (3, 3)]

Note:

On April 19th, many remember moments of persistence and discovery in history. Embrace this challenge with the same spirit—navigate through the obstacles with backtracking and forge your path to success.