使用回溯法实现LeetCode Unique Paths III（JS）时结果不符求助

Let's figure out why your code returns 0 instead of the expected 2 for the test case [[1,0,0,0],[0,0,0,0],[0,0,2,-1]]. There are two key bugs in your implementation:

1. Incorrectly Restoring Grid State During Backtracking #

When you start at the starting cell (value 1), you mark it as visited by setting grid[i][j] = -1, but when backtracking, you set it back to 0 instead of its original value 1. This corrupts the grid for subsequent recursive calls, leading to incorrect path validation.

2. Wrong Zero Count Decrement Logic and End Condition #

• You're decrementing zero_count for every step, even when moving from the starting cell (which isn't a 0). By the time you reach the end cell, your zero_count will be -1 instead of 0, so the condition zero_count == 0 never triggers.
• The end condition doesn't account for the fact that non-zero cells (start or end) shouldn't affect the zero count.

Here's the fixed version of your code:

/**
 * @param {number[][]} grid
 * @return {number}
 */
var uniquePathsIII = function(grid) {
    let m = grid.length, n = grid[0].length;
    let start, target;
    let res = 0;
    let zero_counts = 0;

    // First pass to find start, end, and count zeros
    for(let i = 0; i < m; i++){
        for(let j = 0; j < n; j++){
            if(grid[i][j] === 1){
                start = [i, j];
            } else if(grid[i][j] === 0){
                zero_counts += 1;
            } else if(grid[i][j] === 2){
                target = [i, j];
            }
        }
    }

    const backtrace = (i, j, remaining_zero) => {
        // Out of bounds or hit an obstacle/visited cell
        if(i < 0 || i >= m || j < 0 || j >= n || grid[i][j] === -1){
            return;
        }

        // Check if we've reached the target
        if(i === target[0] && j === target[1]){
            // Only count this path if all zeros are visited
            if(remaining_zero === 0){
                res += 1;
            }
            return;
        }

        // Save original value to restore later
        const originalValue = grid[i][j];
        // Mark current cell as visited
        grid[i][j] = -1;

        // Calculate new remaining zero count: only decrement if current cell was a 0
        const newRemaining = originalValue === 0 ? remaining_zero - 1 : remaining_zero;

        // Explore all four directions
        backtrace(i+1, j, newRemaining);
        backtrace(i-1, j, newRemaining);
        backtrace(i, j+1, newRemaining);
        backtrace(i, j-1, newRemaining);

        // Restore original cell value (backtrack)
        grid[i][j] = originalValue;
    };

    // Start backtracking from start position with total zeros to visit
    backtrace(start[0], start[1], zero_counts);
    return res;
};

Key Fixes Explained: #

1. Grid State Restoration: We now save the original value of each cell before marking it as visited, and restore that exact value during backtracking. This ensures the grid stays valid for all recursive paths.
2. Zero Count Logic: We only decrement the remaining_zero count when stepping on a 0 cell. The starting cell (1) doesn't affect the count since we don't need to revisit it, and the end cell (2) is handled separately in the target check.
3. End Condition: The target check now correctly verifies all zeros have been visited (remaining_zero === 0) before counting the path as valid.

Testing this code with your sample input will return the expected result of 2.

内容的提问来源于stack exchange，提问作者down