Python DFS 调用差异

Question

我试图用Python解决这个涉及DFS的leetcode问题：https://leetcode.com/problems/count-sub-islands/

这是我最初的解决方案，但没有成功：

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

但是，当我像这样在 return 语句中拆分 dfs 调用时，代码就起作用了：

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

有人可以向我解释 dfs 调用之间的区别，因为它们似乎与我相同？谢谢！

我尝试了第一个代码片段，但没有成功。在第二个片段中拆分 dfs 调用后，它起作用了。

Answer 1

这是由

and

的“短路”行为引起的，其中表达式从左到右计算，直到遇到

False

值，之后它将停止计算该表达式。当您分离每个

dfs

调用时，短路行为被绕过，因为每个

dfs

调用都是在

and

表达式之前执行的。但在您的第一个代码中，

and

的短路行为会导致某些

dfs

调用无法执行，从而使您的函数不正确。