使用DFS的岛屿数量

Question

帮助我发现错误

答案错误 细节 输入 实际“ 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

问题是位置与访问无关。 位置是单元格的 content ，而访问应收集单元格的坐标。

因此，将相关部分更改为：

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