Matrix Depth-First Search (DFS) for Unique Paths

Problem: Count unique paths from the top-left to bottom-right of a matrix, avoiding obstacles (1s) and not revisiting cells in the same path.

1. Approach

• DFS with Backtracking:
  • Explore all four directions (up, down, left, right).
  • Track visited cells to avoid cycles.
  • Use recursion to traverse paths and backtrack to reset visited cells.

2. Algorithm

Base Cases

1. Out of Bounds: Row/column < 0 or ≥ matrix dimensions.
2. Obstacle: Current cell is 1.
3. Visited Cell: Revisiting a cell in the current path.
4. Destination Reached: Bottom-right cell.

Steps

1. Check Base Cases: Return 0 for invalid paths or 1 if destination is reached.
2. Mark Current Cell as Visited.
3. Recursively Explore Directions:
   • Up: (row-1, col)
   • Down: (row+1, col)
   • Left: (col-1, row)
   • Right: (col+1, row)
4. Sum Valid Paths from all directions.
5. Unmark Current Cell (backtracking).

3. Code Implementation