Solution: Unique Paths III

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$$m, n$ $\leq 20$

• $1 \leq$ $m \times n$ $\leq 20$

• $-1 \leq$ grid[i][j] $\leq 2$

• There is exactly one starting cell and one ending cell.

Solution

The main goal is to find every possible path that visits each empty square exactly once, without stepping on obstacles or revisiting any cell. This can be done using backtracking, which explores different paths and steps back when a dead end is reached. The first step is identifying the starting square and counting the total number of walkable squares in the grid. Walkable squares include all empty cells (0), the starting square (1), and the ending square (2).

Once the number of walkable squares is determined, the algorithm begins a recursive exploration of all valid paths starting from the starting square. It marks the current square as visited and decreases the count of remaining walkable squares to be visited. This prevents revisiting the same square in the current path. The algorithm then tries to move in one of the four possible directions (up, down, left, and right) while staying within the grid boundaries and avoiding any visited or blocked cells. This leads to two possible outcomes:

• When a new valid square is reached, the process repeats: the new square is marked as visited, and its neighbors are explored recursively, i.e., one of the possible directions is tried.

• The tried direction doesn't lead to a valid path, i.e., the algorithm can't reach any walkable cell. When this happens, the algorithm backtracks in two ways:

  • If there are still unexplored directions from the current square, it restores the current square to its original (unvisited) state so it can be used again in other potential paths. It then tries another direction, for example, if it previously moved upward, it might now try moving downward, right, or left.

  • If all directions from the current square have already been tried and none lead to a valid path, the algorithm backtracks to the previous square and continues exploring any remaining unexplored directions from there.

The base case of this recursive exploration is reached when only one walkable square remains, and that square is the ending square (i.e., its value is 2). At that moment, the path is counted as valid.

After a valid path is found, the algorithm does not explore further from the ending square, but it still automatically backtracks to the previous square when the recursion unwinds. This is important because other unexplored directions may be earlier in the path that could lead to different valid routes. Eventually, this ensures that all possible valid paths are discovered and counted.

Let's look at the algorithm steps:

1. Initialize variables:

   1. Set totalWalkableSquares to 0 to count all non-obstacle squares (including start and end).

   2. Set startX and startY to 0 as placeholders for the starting square’s position.

2. Traverse each cell in the grid. For each cell in the grid:

   1. If the cell is not an obstacle (0, 1, or 2), increase totalWalkableSquares by 1.

   2. If the cell is the starting point (1), update startX and startY to its coordinates.

3. Start exploring the valid paths from the starting square by calling the recursive function explorePaths() with the current grid, startX, startY, and totalWalkableSquares. The explorePaths() function works as follows:

   1. For the base case, if the current square is the ending square (2) and only one square is left to visit (remainingWalkableSquares == 1), return 1 to count this as a valid path.

   2. Mark the current square as visited by temporarily storing its value and setting it to a marker, -4. This in-place marking helps avoid using extra space for tracking visited cells. Decrease remainingWalkableSquares by 1 as this square is now considered visited.

   3. Once the cell is marked visited, explore all four directions. For each direction (up, down, left, right):

      1. Compute the new position.

      2. If the new position is inside the grid and not an obstacle or already visited, recursively call explorePaths() for the new position with the updated remainingWalkableSquares value. Add the result to the total path count.

   4. Backtrack, i.e., restore the cell to its original value so it can be used again in a different path.

   5. Return the total number of valid paths from this point.

4. Return the final result from the initial call.

The slides below help to understand the solution in a better way.