独特路径II-DFS方法

Question

我试图解决以下问题https://leetcode.com/problems/unique-paths-ii/

问题如下：障碍物和空间在网格中分别标记为1和0。

输入：障碍物网格=[[0,0,0]，[0,1,0]，[0,0,0]]

产出：2

说明：

在上面的3x3网格的中间有一个障碍。有两种方法可以到达右下角：

1. 对-

我的DFS解决方案如下，但它返回1而不是2。我想知道我在以下方法中错过了什么？

class Solution {
    func uniquePathsWithObstacles(_ obstacleGrid: [[Int]]) -> Int {
        var column = obstacleGrid[0].count
        var row = obstacleGrid.count
        var visited = Array(repeating: Array(repeating: false, count:column), count: row)
        return dfs(obstacleGrid, 0, 0, &visited)
    }
    
    func dfs(_ obstacleGrid: [[Int]], _ i: Int, _ j: Int, _ visited: inout [[Bool]]) -> Int {
        if i < 0 || i >= obstacleGrid.count || j < 0 || j >= obstacleGrid[0].count || obstacleGrid[i][j] == 1 || visited[i][j] == true {
            return 0
        } 
        
        visited[i][j] = true

        if i == obstacleGrid.count - 1 && j == obstacleGrid[0].count - 1 {
          return 1
        }
        
        return dfs(obstacleGrid, i+1, 0, &visited) + 
        dfs(obstacleGrid, i-1, 0, &visited) +
        dfs(obstacleGrid, i, j+1, &visited) +
        dfs(obstacleGrid, i, j-1, &visited)
    }
}

Answer 1

如果访问[i][j]看起来不正确，则返回0。您应该记住已访问单元格的返回值，并在以后调用该单元格时再次返回。原因是你可以通过不同的路径到达那个细胞，而每一条路径都应该对结果有所贡献。

代码返回1是有道理的，因为第二次到达右下角的单元格时，您将返回0，因为在发现前一条路径的过程中，该单元格已被“访问”。