https://leetcode.com/problems/number-of-islands/

Given an m x n 2d grid map of ‘1’s (land) and ‘0’s (water), return the number of islands.

An island is surrounded by water and is formed by connecting adjacent lands horizontally or vertically. You may assume all four edges of the grid are all surrounded by water.

思路,BFS,每次遇到 1 时就搜索范围内所有的 1 并将其值改为 0 (这样就不需要维护一个 visited),直到全部遍历完成。

class Solution:
    def numIslands(self, grid: List[List[str]]) -> int:

        count = 0
        directions = [[1,0],[-1,0],[0,1],[0,-1]]
        for i in range(len(grid)):
            for j in range(len(grid[0])):
                if grid[i][j] == "1":
                    count += 1

                    #bfs
                    q = []
                    q.append([i,j])
                    while len(q)> 0:
                        m,n = q.pop(0)

                        for d in directions:
                            if 0 <= m+d[0] < len(grid) and 0 <= n+d[1] < len(grid[0]) and grid[m+d[0]][n+d[1]] == "1":
                                grid[m+d[0]][n+d[1]] = "0"
                                q.append([m+d[0],n+d[1]])

        return count