题解 | #岛屿数量#

算法思想一：深度优先搜索

解题思路：

可以将二维网格看成一个无向图，竖直或水平相邻的 1 之间有边相连。
为了求出岛屿的数量，可以扫描整个二维网格。如果一个位置为 1，则以其为起始节点开始进行深度优先搜索（四周）。在深度优先搜索的过程中，每个搜索到的 1 都会被重新标记为 0。
最终岛屿的数量就是我们进行深度优先搜索的次数。

图解：

代码展示：

JAVA版本

import java.util.*;
public class Solution {
    /**
     * 判断岛屿数量
     * @param grid char字符型二维数组 
     * @return int整型
     */
    // 深度优先搜索
    void dfs(char[][] grid, int r, int c) {
        int nr = grid.length;
        int nc = grid[0].length;
        // 边界限定
        if (r < 0 || c < 0 || r >= nr || c >= nc || grid[r][c] == '0') {
            return;
        }
        // 遍历过的点变为 0
        grid[r][c] = '0';
        // 递归
        dfs(grid, r - 1, c);
        dfs(grid, r + 1, c);
        dfs(grid, r, c - 1);
        dfs(grid, r, c + 1);
    }
    public int solve (char[][] grid) {
        // write code here
        // 特殊情况
        if (grid == null || grid.length == 0) {
            return 0;
        }
        int nr = grid.length;
        int nc = grid[0].length;
        int num_islands = 0;
        // 双层循环
        for (int r = 0; r < nr; ++r) {
            for (int c = 0; c < nc; ++c) {
                if (grid[r][c] == '1') {
                    ++num_islands;
                    // 深度递归遍历
                    dfs(grid, r, c);
                }
            }
        }
        return num_islands;
    }
}

复杂度分析

时间复杂度 $O(MN)$ ：其中 M 和 N 分别为行数和列数，双重遍历时间

空间复杂的 $O(MN)$ ：在最坏情况下，整个网格均为陆地，深度优先搜索的深度达到MN

算法思想二：广度优先搜索

解题思路：

同样地，也可以使用广度优先搜索代替深度优先搜索。
为了求出岛屿的数量，我们可以扫描整个二维网格。如果一个位置为 1，则将其加入队列，开始进行广度优先搜索。在广度优先搜索的过程中，每个搜索到的 1 都会被重新标记为 0。直到队列为空，搜索结束。
最终岛屿的数量就是我们进行广度优先搜索的次数。

代码展示：

Python版本

import collections
#
# 判断岛屿数量
# @param grid char字符型二维数组 
# @return int整型
#
class Solution:
    def solve(self , grid ):
        # write code here
        nr = len(grid)
        if nr == 0:
            return 0
        nc = len(grid[0])
        # 初始化
        num_islands = 0
        # 双层遍历
        for r in range(nr):
            for c in range(nc):
                if grid[r][c] == "1":
                    num_islands += 1
                    # 将 1 变为 0
                    grid[r][c] = "0"
                    # 将该位置加入队列
                    neighbors = collections.deque([(r, c)])
                    while neighbors:
                        # 出队列
                        row, col = neighbors.popleft()
                        for x, y in [(row - 1, col), (row + 1, col), (row, col - 1), (row, col + 1)]:
                            if 0 <= x < nr and 0 <= y < nc and grid[x][y] == "1":
                                neighbors.append((x, y))
                                grid[x][y] = "0"
        return num_islands

复杂度分析

时间复杂度 $O(MN)$ ：其中 M 和 N 分别为行数和列数，双重遍历时间

空间复杂的 $O(min(M,N))$ ：在最坏情况下，整个网格均为陆地，队列的大小可以达到 $min(M,N)$ 。