Python中DFS两种调用写法的差异解析——LeetCode子岛屿计数问题

问题场景 #

在解决计数子岛屿问题时，两段逻辑看似一致的DFS代码出现了不同结果：直接通过and串联返回多个DFS调用的写法测试用例失败，而先将每个DFS调用结果存入变量再返回的写法成功。

初始失败代码 #

from typing import List

class Solution:
    def countSubIslands(self, grid1: List[List[int]], grid2: List[List[int]]) -> int:
        ans = 0

        def dfs(i, j):
            if not (0 <= i < len(grid1) and 0 <= j < len(grid1[0]) and grid2[i][j]):
                return True
            if (not grid2[i][j] and grid1[i][j]) or (grid2[i][j] and not grid1[i][j]):
                return False
            if grid1[i][j] and grid2[i][j]:
                grid2[i][j] = 0
                return dfs(i+1,j) and dfs(i-1,j) and dfs(i,j+1) and dfs(i,j-1)
         
        for i in range(len(grid2)):
            for j in range(len(grid2[0])):
                if grid2[i][j] and dfs(i,j):
                    ans += 1
        return ans

修改后成功代码 #

from typing import List

class Solution:
    def countSubIslands(self, grid1: List[List[int]], grid2: List[List[int]]) -> int:
        ans = 0

        def dfs(i, j):
            if not (0 <= i < len(grid1) and 0 <= j < len(grid1[0]) and grid2[i][j]):
                return True
            if (not grid2[i][j] and grid1[i][j]) or (grid2[i][j] and not grid1[i][j]):
                return False
            if grid1[i][j] and grid2[i][j]:
                grid2[i][j] = 0
                # return dfs(i+1,j) and dfs(i-1,j) and dfs(i,j+1) and dfs(i,j-1)
                one = dfs(i+1,j)
                two = dfs(i-1,j)
                three = dfs(i,j+1)
                four = dfs(i,j-1)
                return one and two and three and four

        for i in range(len(grid2)):
            for j in range(len(grid2[0])):
                if grid2[i][j] and dfs(i,j):
                    ans += 1
        return ans

核心差异：Python的短路求值特性 #

问题的根源在于Python中and运算符的短路求值行为：

• 当使用return a and b and c and d时，如果a的结果为False，Python会直接返回False，不会执行后续的b、c、d表达式。
• 这种行为会导致失败代码中，一旦某个方向的DFS返回False，其余三个方向的DFS不会被执行，对应位置的grid2[i][j]也不会被标记为0（即未被标记为已访问）。

失败代码的具体问题 #

当某个岛屿的一部分不满足子岛屿条件（导致DFS返回False），短路求值会跳过其他方向的DFS遍历：

1. 未被遍历的grid2中的1仍然保持为1，没有被标记为已访问。
2. 后续外层循环遍历到这些位置时，会再次触发DFS，错误地将它们当作新的岛屿进行判断，最终导致子岛屿计数错误。

成功代码的解决逻辑 #

修改后的代码先依次执行四个方向的DFS：

1. 不管某个方向的DFS结果是True还是False，四个方向的DFS都会完整执行，所有grid2中的1都会被标记为0。
2. 后续外层循环不会再处理这些已访问的位置，确保每个岛屿只会被判断一次，计数结果正确。

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