DFS图遍历中visited集合放置错误导致岛屿周长计算异常求助

问题描述 #

我无法理解为何将visited.add((i,j))放在else分支时能得到正确输出，而放在如下代码所示的位置会得到错误结果。已尝试用示例[[0,1],[1,1]]进行调试，但仍未找到原因。

错误代码 #

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))  # 放在此处会导致错误结果，移到else分支才正确

            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)
                # 上下左右四个方向

        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]]))

错误原因分析 #

核心问题在于你提前将无效格子标记为已访问：

• 当前代码中，在判断(i,j)是否为越界/水域（0）之前，就把(i,j)加入了visited集合。
• 这意味着那些不属于岛屿的格子（越界位置、水域）会被错误标记为已访问。后续当合法的岛屿格子访问这些相邻的无效格子时，会因为(i,j) in visited直接返回0，而不是正确返回1（代表该边属于岛屿周长的一部分）。

拿测试用例[[0,1],[1,1]]举例：

1. 从(0,1)开始DFS，将其加入visited后，递归访问左侧的(0,0)（水域）。
2. (0,0)不在visited，被加入集合，随后判断是水域，返回1。
3. 当处理(1,0)这个岛屿格子时，访问上方的(0,0)，此时(0,0)已经在visited中，直接返回0，但实际上(1,0)的上方是水域，应该贡献1条周长边，这就导致最终结果少算了这条边，输出错误。

修正后的代码 #

将visited.add((i,j))移到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
            
            if i < 0 or j < 0 or i >= ni or j >= nj or grid[i][j] == 0:
                return 1
            
            else:
                visited.add((i,j))  # 仅标记有效岛屿格子
                return dfs(i-1, j) + dfs(i+1, j) + dfs(i, j-1) + dfs(i, j+1)

        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]]))

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