图遍历DFS中访问节点集的位置不正确

Question

我无法理解为什么将

visited.append((i,j))

放在 else 情况下会给出正确的输出，而保持如下所示会给出错误的输出。 我尝试用一个更简单的示例进行调试 [[0,1], [1,1]] 但我无法弄清楚为什么将其保留在 else 之外会产生错误的结果。 代码：

from typing import List


class Solution:
    def islandPerimeter(self, grid: List[List[int]]) -> int:
        ni, nj = len(grid), len(grid[0])
        visited = set()
        def dfs(i, j):
            nonlocal visited

            if (i,j) in visited:
                return 0
            
            visited.add((i,j))  # Placing this inside else gives me right result

            if i < 0 or j < 0 or i >= ni or j >= nj or grid[i][j] == 0:
                return 1
            
            else:
                return dfs(i-1, j) + dfs(i+1, j) + dfs(i, j-1) + dfs(i, j+1)
                # U D L R

        for i in range(len(grid)):
            for j in range(len(grid[i])):
                if grid[i][j] == 1:
                    return dfs(i, j)
                
print(Solution().islandPerimeter([[0,1], 
                                  [1,1]]))

Answer 1

如果我不得不猜测，这可能与您返回

1

而不是

0

的事实有关，具体取决于是否访问了空/越界位置。

以这个例子为例：

 01
 11

您将在以下位置返回

1

：

  *
 *1*
*11*
 **

那是多少个职位？嗯，这取决于你如何计算它们。如果您对每个位置精确计数一次（访问的是 else 之外），则会有 7 个位置。

如果每次与

1

相邻（访问的是

else

的 inside）时数一下，将会有 8：

  A
 G1B
F11C
 ED

A到F各算一次（总共6个），但G会算两次（从右边访问一次，从底部访问一次）。

这就是为什么清楚你所计算的内容如此重要。我想你被要求确定这个形状的周长，它将是 8，而不是 7：

   _
 _| |
|_ _|