Description

Given a boolean 2D matrix, 0 is represented as the sea, 1 is represented as the island. If two 1 is adjacent, we consider them in the same island. We only consider up/down/left/right adjacent.

Find the number of islands.

Example
Example 1:

Input:
[
[1,1,0,0,0],
[0,1,0,0,1],
[0,0,0,1,1],
[0,0,0,0,0],
[0,0,0,0,1]
]
Output:
3
Example 2:

Solution

使用bfs可以较好解决，需注意模板格式 queue和visit永远同时更新

from collections import deque
class Solution:
    """
    @param grid: a boolean 2D matrix
    @return: an integer
    """
    def numIslands(self, grid):
        # write your code here
        if not grid or not grid[0]:
            return 0
        visited = set()    
        cnt = 0
        
        for i in range(len(grid)):
            for j in range(len(grid[0])):
                if grid [i][j] and (i,j) not in visited:
                    self.bfs(i,j,grid,visited)
                    cnt +=1
                    
        return cnt  
    def bfs(self,i,j,grid,visited):
        queue=deque([(i,j)])
        visited.add((i,j))
        while queue:
            a,b = queue.popleft()
            for pos in [(0,1),(1,0),(-1,0),(0,-1)]:
                x= a+pos[0]
                y= b+pos[1]
                if not self.is_valid(x,y,grid,visited):
                    continue
                queue.append((x,y))
                visited.add((x,y))
    
    def is_valid(self,x,y,grid,visited):
        n, m = len(grid), len(grid[0])
        if not (0 <= x < n and 0 <= y < m):
            return False
        if (x, y) in visited:
            return False
        return grid[x][y]