Solution: Unique Paths III

Explore how to implement a backtracking algorithm to count all unique four-directional paths in a grid from a start to end cell while visiting each empty square exactly once. Understand how to mark visited cells in-place, recursively explore valid directions, and backtrack effectively to discover all possible paths. This lesson helps you develop key problem-solving skills for similar grid-based coding interview problems.

We'll cover the following...

Statement
Solution
- Time complexity
- Space complexity

Statement

You are given a $m \times n$ integer array, grid, where each cell, grid[i][j], can have one of the following values:

1 indicates the starting point. There is exactly one such square.
2 marks the ending point. There is exactly one such square.
0 represents empty squares that can be walked over.
-1 represents obstacles that cannot be crossed.

Your task is to return the total number of unique four-directional paths from the starting square (1) to the ending square (2), such that every empty square is visited exactly once during the walk.

Constraints:

$m$ $==$ grid.length
$n$ $==$ grid[i].length
$1 \leq$ ...