200. Number of Islands

Loading...LeetCode

本质上是无向强连通图，每个格子都是个node，遍历所有格子，遇到值=1的就算一个岛，然后从这个node开始BFS往下搜，值=1加进queue继续，0就停。同时要维护一个全局的visited集合。

class Solution:
    def numIslands(self, grid: List[List[str]]) -> int:
        if not grid or not grid[0]: return 0
        
        res = 0
        visited = set()
        w, h = len(grid), len(grid[0])
        
        def validNeighbors(x, y):
            applicants = [(x+1, y), (x-1, y), (x, y+1), (x, y-1)]
            valid = []
            for a in applicants:
                if a not in visited and a[0]>=0 and a[0]<w and a[1]>=0 and a[1]<h:
                    valid.append(a)
            return valid
        
        for i in range(w):
            for j in range(h):
                if (i, j) in visited:
                    continue
                else:
                    if grid[i][j] == '1':
                        res += 1
                        queue = collections.deque([(i,j)])
                        while queue:
                            x, y = queue.popleft()
                            visited.add((x,y))
                            togo = validNeighbors(x, y)
                            if togo:
                                for next_ in togo:
                                    if grid[next_[0]][next_[1]] == '1':
                                        queue.append(next_)
                                    visited.add(next_)
        return res