使用 DFS 的岛屿数量

Question

帮我找出错误

答案错误细节输入 [["1","1","0","0","0"],["1","1","0","0","0"],["0", "0","1","0","0"],["0","0","0","1","1"]] 输出 1个预期的 3

使用深度优先遍历来计算岛屿数量

class Solution:
    def numIslands(self, grid: List[List[str]]) -> int:
        #Nested loop to go over our Grid
        #use depth first traversal in second loop to explore neighbors
        
        visited = set()
        count = 0
        
        for row in range(len(grid)):
            for col in range(len(grid[0])):
                if (self.explore(grid,row,col,visited)):
                    count +=1 
        return count
                
    def explore(self,grid,row,col,visited):
        #catch if we are out of bounds
        rowInbound = 0 <= row and row < len(grid)
        colInbound = 0 <= col and col < len(grid[0])
        
        if not rowInbound or not colInbound:
            return False
        
        #check if current is water
        position = grid[row][col]
        if (position == '0'):
            return False
        
        #check for visited 
        if position in visited:
            return False
        
        visited.add(position)
        
        self.explore(grid,row-1,col,visited)
        self.explore(grid,row+1,col,visited)
        self.explore(grid,row,col-1,visited)
        self.explore(grid,row,col+1,visited)
        
        #this true will symbolize that I am now exploring a new island
        
        return True

Answer 1

问题是position和visited没有关系。 position是一个单元格的内容，而visited应该收集一个单元格的坐标。

所以将相关部分改为：

    if (row, col) in visited:
        return False
    
    visited.add((row, col))

使用 DFS 的岛屿数量

Number of Islands using DFS

python

depth-first-search