岛屿数量

岛屿数量_牛客题霸_牛客网

问题简述

给一个01矩阵，1代表是陆地，0代表海洋， 如果两个1相邻，那么这两个1属于同一个岛。我们只考虑上下左右为相邻。
岛屿: 相邻陆地可以组成一个岛屿（相邻:上下左右） 判断岛屿个数。

思路1：DFS

• 假设从岛屿的任意一点出发，上下左右深度遍历周围的点，遇到 1 就更新为 0，直到将整个岛屿置为 0；

• 遍历 grid 上的每个点，如果是 1 就执行上述 dfs；

• 记录遇到的岛屿数量；

Python

class Solution:
    def solve(self , grid: List[List[str]]) -> int:
        if not grid: return 0
        
        m, n = len(grid), len(grid[0])
        
        def dfs(i, j):
            if 0 <= i < m and 0 <= j < n and grid[i][j] == '1':
                grid[i][j] = '0'
                dfs(i - 1, j)
                dfs(i, j - 1)
                dfs(i + 1, j)
                dfs(i, j + 1)
        
        ret = 0
        for i in range(m):
            for j in range(n):
                if grid[i][j] == '1':
                    ret += 1
                    dfs(i, j)
        
        return ret

思路2：BFS

• 思路同 DFS，将 dfs 遍历岛屿替换为 bfs 遍历；

Python

class Solution:
    def solve(self , grid: List[List[str]]) -> int:
        if not grid: return 0
        
        m, n = len(grid), len(grid[0])
        
        from collections import deque
        
        def bfs(i, j):
            q = deque()
            q.append((i, j))
            while q:
                i, j = q.popleft()
                if 0 <= i < m and 0 <= j < n and grid[i][j] == '1':
                    grid[i][j] = '0'
                    q.append((i - 1, j))
                    q.append((i, j - 1))
                    q.append((i + 1, j))
                    q.append((i, j + 1))
                    
        ret = 0
        for i in range(m):
            for j in range(n):
                if grid[i][j] == '1':
                    ret += 1
                    bfs(i, j)
        
        return ret