Unique Paths III

class Solution {
    int rLen, cLen;
    int[][] matrix;
    int totalPaths;
    
    protected void searchPaths(int r, int c, int remaining) {
        if (matrix[r][c] == 2 && remaining == 1) {
            totalPaths += 1;
            return;
        }
    
        int tmp = matrix[r][c];
        matrix[r][c] = -4;
        remaining -= 1;
    
        int[] deltasR = {0, 0, 1, -1};
        int[] deltasC = {1, -1, 0, 0};
        for (int i = 0; i < 4; i++) {
            int newR = r + deltasR[i];
            int newC = c + deltasC[i];
    
            if (0 > newR || newR >= rLen || 0 > newC || newC >= cLen)
                continue;
    
            if (matrix[newR][newC] < 0)
                continue;
    
            searchPaths(newR, newC, remaining);
        }
    
        matrix[r][c] = tmp;
    }
    
    public int uniquePathsIII(int[][] grid) {
        int freeSpaces = 0, startR = 0, startC = 0;
    
        rLen = grid.length;
        cLen = grid[0].length;
    
        for (int r = 0; r < rLen; ++r)
            for (int c = 0; c < cLen; ++c) {
                int cell = grid[r][c];
                if (cell >= 0)
                    freeSpaces += 1;
                if (cell == 1) {
                    startR = r;
                    startC = c;
                }
            }
    
        totalPaths = 0;
        matrix = grid;
    
        searchPaths(startR, startC, freeSpaces);
    
        return totalPaths;
    }
}

The given Java solution resolves the "Unique Paths III" problem by finding all unique paths from a start point to an endpoint on a grid while traversing all non-obstacle spaces exactly once. Below is a summary of how the solution is implemented:

• Define global variables for grid dimensions (rLen and cLen), the grid itself (matrix), and to keep track of the total number of paths (totalPaths).

• Implement a recursive helper function searchPaths:

  • End the recursion and increment totalPaths if the end cell (2) is reached and all cells (sans obstacles) have been visited.
  • Mark the current cell as visited by setting it to -4 and adjust the count of remaining cells.
  • Define possible moves (up, down, left, right) using two integer arrays (deltasR and deltasC).
  • For each possible move, check validity (cell not out of bounds or already visited) before recursively searching the grid.
  • After exploring, reset the current cell to its original value to allow other paths to reuse this cell in their exploration.

• The uniquePathsIII method:

  • Initialize counters for free spaces (non-obstacles) and determine the starting coordinates.
  • Initialize the grid (matrix) and global variables.
  • Kick off the solution by calling the searchPaths method from the start coordinates with the total number of free spaces as the parameter to track the number of cells left to visit.
  • Finally, return the count of all distinct paths that span all non-obstacle cells exactly once and end at the endpoint.

This method efficiently explores all possible paths using backtracking, ensuring each valid path is counted once all constraints are satisfied. The recursive nature paired with careful state management (marking and unmarking visited cells) allows the solution to avoid revisiting configurations that have already been explored, ensuring optimal performance for larger grids.

class Explorer:
    def countUniquePaths(self, matrix: List[List[int]]) -> int:
        total_rows, total_columns = len(matrix), len(matrix[0])
    
        # Initialize the variables needed for the traversal process
        open_cells = 0
        entry_row, entry_col = 0, 0
        for r in range(total_rows):
            for c in range(total_columns):
                point = matrix[r][c]
                if point != -1:
                    open_cells += 1
                if point == 1:
                    entry_row, entry_col = r, c
    
        # Initialize the counter for the number of valid paths
        routes = 0
    
        # Recursive function to perform the backtrack search
        def backtrack(current_row, current_col, remaining):
            nonlocal routes
    
            # Check completion condition
            if matrix[current_row][current_col] == 2 and remaining == 1:
                # Completing the path successfully
                routes += 1
                return
    
            # Mark this cell as visited
            original = matrix[current_row][current_col]
            matrix[current_row][current_col] = -3
            remaining -= 1
    
            # Iterate through possible moves
            for delta_row, delta_col in [(0, 1), (0, -1), (1, 0), (-1, 0)]:
                new_row, new_col = current_row + delta_row, current_col + delta_col
    
                # Check bounds and cell state
                if not (0 <= new_row < total_rows and 0 <= new_col < total_columns) or matrix[new_row][new_col] < 0:
                    continue
    
                backtrack(new_row, new_col, remaining)
    
            # Undo the visit
            matrix[current_row][current_col] = original
    
        backtrack(entry_row, entry_col, open_cells)
    
        return routes

The provided Python code defines a class Explorer which includes a method countUniquePaths used to find all unique paths from a starting point to an endpoint in a grid, traversing every non-blocked cell exactly once. The grid cells can be free, blocked, a starting entry, or a destination and are represented as integers (0 for open, -1 for blocked, 1 for start, and 2 for end).

• The method initializes essential variables to keep track of grid dimensions, count of traversable cells, and starting position coordinates.
• Utilizes a depth-first search (DFS) technique with backtracking:
  • The recursive function backtrack is defined within countUniquePaths to handle the path exploration, altering its behavior based on the current cell's value and the remaining number of cells to visit.
  • If the endpoint is reached and all open cells have been traversed, this valid path increments the path counter.
  • To avoid revisiting cells and manage path tracing, cells are temporarily marked as visited (-3), and reverted back to their original state after recursion.
  • The function explores possible moves in four directions (up, down, left, right), carefully checking boundaries and cell states to avoid moving into blocked or visited locations.
• At the end of the exploration, the total number of valid paths found is returned.

This approach guarantees that all potential paths are explored while maintaining an efficient traversal of the grid by skipping over non-viable paths early. The usage of recursion and backtracking makes it a fit for smaller grids where paths are computationally feasible to enumerate.