200. 岛屿数量

Posted on Edited on In Views: Word count in article: 829 Reading time ≈ 1 mins.

200. 岛屿数量

题目链接：200. 岛屿数量

题目描述

给你一个由 '1'（陆地）和 '0'（水）组成的的二维网格，请你计算网格中岛屿的数量。
岛屿总是被水包围，并且每座岛屿只能由水平方向和/或竖直方向上相邻的陆地连接形成。
此外，你可以假设该网格的四条边均被水包围。

核心思考：网格遍历之沉岛策略 (DFS)

面对此类相连成片的矩阵区域统计题型，最常用也极具巧思的解法就是深度优先搜索 (DFS) 的“沉岛法”或是称其为污染法。

我们的主要目标是扫描整个矩阵：

  1. 采用两层循环从头开始找目标。一旦遇到一块未踏足过的网格为 '1'，由于这是岛屿的一份碎片，这就意味着我们发现了一座全新的孤岛，于是立刻让岛屿计数器 ans += 1。
  2. 发现岛屿后，紧随其后的就是立刻启动一次深入的 DFS 蔓延探测。
  3. DFS 函数的核心职责不是为了在这座岛上收集战利品，而是负责将被发现这块陆地区域相连的所有同伴全部“无情连坐击沉”。
    • 将脚下的 '1' 强行翻转修改为 '2'（或是随意其他非1字符如 '0'），标志着“这里已经被征服发现了，下次路过不用再查我”。
    • 只要是陆地就继续向它的上下左右四个方向进行递归。
    • 这就保证了我们在外层遍历这张图的其它格点时，不会再把这座岛的其他脚丫子误认为是别的岛屿产生重复统计计数循环。

解题思路 (Python)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution:
    def numIslands(self, grid: List[List[str]]) -> int:
        m = len(grid)
        n = len(grid[0])

        def dfs(i,j):
            if i<0 or i>=m or j<0 or j>=n or grid[i][j] != "1":
                return
            grid[i][j] = "2" # 击沉岛屿
            dfs(i-1,j)
            dfs(i+1,j)
            dfs(i,j+1)
            dfs(i,j-1)

        ans = 0
        for i, row in enumerate(grid):
            for j,v in enumerate(row):
                if v == "1":
                    dfs(i,j)
                    ans += 1
        return ans

复杂度分析

  • 时间复杂度：O(M * N)，其中 M 和 N 分别为二维矩阵网格的长宽跨度。借助沉岛机制杜绝走回头路，每个网格坐标元素仅会被极有限次访问。
  • 空间复杂度：O(M * N)，最坏退化下（比如一整面大空地全都是 "1" 连体长龙式的大陆块），在纵深顺路推进的递归操作栈最深处可以保留接近整个格点容积 O(M*N) 的调用记录。

ACM 模式

本节提供 ACM 竞赛风格的完整可运行代码，包含输入输出处理。

输入格式：

1
2
3
4
5
m n
a11 a12 a13 ... a1n
a21 a22 a23 ... a2n
...
am1 am2 am3 ... amn

第一行输入矩阵的行数 m 和列数 n，随后输入 m 行 n 列的矩阵元素。

完整代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
import sys

class Solution:
    def numIslands(self, grid: List[List[str]]) -> int:
    m = len(grid)
            n = len(grid[0])

            def dfs(i,j):
                if i<0 or i>=m or j<0 or j>=n or grid[i][j] != "1":
                    return
                grid[i][j] = "2" # 击沉岛屿
                dfs(i-1,j)
                dfs(i+1,j)
                dfs(i,j+1)
                dfs(i,j-1)

            ans = 0
            for i, row in enumerate(grid):
                for j,v in enumerate(row):
                    if v == "1":
                        dfs(i,j)
                        ans += 1
            return ans

def main():
    data = sys.stdin.read().strip().split()
    m, n = int(data[0]), int(data[1])
    idx = 2
    matrix = []
    for i in range(m):
        row = list(map(int, data[idx:idx+n]))
        matrix.append(row)
        idx += n

    sol = Solution()
    result = sol.numIslands(matrix)
    print(result)

if __name__ == "__main__":
    main()

运行示例：

1
echo -e "3 3\n1 2 3\n4 5 6\n7 8 9" | python solution.py