算法问题：独特的路径三。在javascript中使用回溯模式并且不起作用

Question

在二维上

1表示起始正方形。

2代表结束方块。

0代表我们可以走过的空方块。

-1代表我们无法跨越的障碍。

返回四向行走的次数

来源：力扣（LeetCode）链接：https://leetcode-cn.com/problems/unique-paths-iii

我正在尝试使用回溯模式来解决这个问题

这是我的代码

/**
 * @param {number[][]} grid
 * @return {number}
 */
var uniquePathsIII = function(grid) {
    let m = grid.length,
        n = grid[0].length;
    let start, targetIndex1,targetIndex2;
    let res = 0;
    let zero_counts = 0;
    
    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){
                targetIndex1 = i;
                targetIndex2 = j;
            }
        }
    }

    const backtrace = (i, j, zero_count) => {
        if( i < 0 || i >= m || 
            j < 0 || j >= n || 
            grid[i][j] == -1 || zero_count < 0)
        {
            return;
        }

        if(i == targetIndex1 && j == targetIndex2 ){
            if(zero_count == 0)
            {
                console.log("yes")
                res += 1;
            }
            return
        }
        
        grid[i][j] = -1;
        backtrace(i+1, j, zero_count - 1)
        backtrace(i-1, j, zero_count - 1)
        backtrace(i, j+1, zero_count - 1)
        backtrace(i, j-1, zero_count - 1)

        grid[i][j] = 0;
    }

    backtrace(start[0], start[1], zero_counts);

    return res;
};

测试样本:

[[1,0,0,0],[0,0,0,0],[0,0,2,-1]]

预期结果：2

结果： 0

Answer 1

或许更简单的解决方案是使用深度优先搜索来解决唯一路径III，如此处所示。

这个概念是，你取一个点，然后向各个方向移动，直到你遇到一个障碍物。

内脏如下：

int totalPaths = dfs(grid, x+1, y,   zero) +
                 dfs(grid, x,   y+1, zero) +
                 dfs(grid, x-1, y,   zero) +
                 dfs(grid, x,   y-1, zero);