Number of Islands的DFS终止条件

求教下，用DFS来求解Number of Islands的时候，DFS的终止条件是什么呢？什么时候DFS会返回，而后再执行外面的FOR LOOP，这个一直没整明白。因为有时候用DFS来解其他类似的题目的时候会碰到MAXIMUM RECURSION DEPTH EXCEEDED.

        def dfs(grid,i,j):
            dirs=[[-1,0],[1,0],[0,1],[0,-1]]
            grid[i][j]='0'
            for dir in dirs:
                nr, nc=i+dir[0],j+dir[1]
                if nr>=0 and nc>=0 and nr<len(grid) and nc<len(grid[0]):
                    if grid[nr][nc]=='1':
                        dfs(grid,nr,nc)
        res=0
        for i in range(len(grid)):
            for j in range(len(grid[0])):
                if grid[i][j]=='1':
                    dfs(grid,i,j)
                    res+=1
        return res   

上下左右子节点的值都是 0 的时候终止

这题推荐BFS，DFS可能深度会深。

当前访问的节点如果是非有效节点就要退出。对于矩阵类型，非有效节点一般指
1: 超出边界
2: 已经访问过
3: 此节点不需要访问。
对于此题，2和3的条件就是此节点是0.

The function you defined as dfs(), in the function, you covered 4 kinds of situation, and the other situation you did not coverd , is the "END" of this path, and it will return nothing.

多谢各位的回复。比如说994. Rotting Oranges这到题，按理说也可以用类似的DFS来解，

        def dfs(grid,i,j,cnt):
            grid[i][j]==2
            dirs=[[-1,0],[0,-1],[1,0],[0,1]]
            for dir in dirs:
                nr=i+dir[0]
                nc=j+dir[1]
                if nr>=0 and nr<len(grid) and nc>=0 and nc<len(grid[0]):
                    if grid[nr][nc]==1:
                        dfs(grid,nr,nc,cnt)
            cnt=cnt+1            
                        
        
        # no fresh orange to start
        if grid[0][0]!=2:
            return 0
        
        res=0
        cnt=0
        for i in range(len(grid)):
            for j in range(len(grid[0])):
                if grid[i][j]==2:
                    dfs(grid,i,j,cnt)
                    res+=1
        
        if res==1:
            return -1
        if res==0:
            return cnt

但这个程序会出现MAXIMUM RECURSION DEPTH EXCEEDED的ERROR，还是有点糊涂

dfs函数没有写终止的情况啊，就是都做走不通时候需要return，要不然就会一直dfs然后就stack overflow了😂
帮你改了一下，发现dfs最后加个return就行了

1.         def dfs(grid,i,j):
   
2.             dirs=[[-1,0],[1,0],[0,1],[0,-1]]
   
3.             grid[i][j]='0'
   
4.             for dir in dirs:
   
5.                 nr, nc=i+dir[0],j+dir[1]
   
6.                 if nr>=0 and nc>=0 and nr<len(grid) and nc<len(grid[0]):
   
7.                     if grid[nr][nc]=='1':
   
8.                         dfs(grid,nr,nc)
   
9.             return
   
10.         res=0
    
11.         for i in range(len(grid)):
    
12.             for j in range(len(grid[0])):
    
13.                 if grid[i][j]=='1':
    
14.                     dfs(grid,i,j)
    
15.                     res+=1
    
16.         return res   

复制代码

[/i][/i]

谢谢分享