Python面试宝典第15题：岛屿数量

题目

        在二维网格地图上，'1' 表示陆地，'0' 表示水域。如果相邻的陆地可以水平或垂直连接，则它们属于同一块岛屿。请进行编码，统计地图上的岛屿数量。比如：下面的二维网格地图，其岛屿数量为3。

基础知识

        解决这类问题的一种常见方法是：深度优先搜索（DFS）或广度优先搜索（BFS）。深度优先搜索和广度优先搜索是图和树型结构中两种基本的遍历算法，广泛应用于各种问题解决场景中，比如：路径查找、图的连通性分析、游戏AI等。下面，我们介绍下深度优先搜索和广度优先搜索的基础知识。

        深度优先搜索是一种探索策略，算法会尽可能深地探索图的分支，直到到达叶子节点或无法继续深入为止，然后回溯以探索其他分支。这个过程类似于树的前序遍历，先访问子节点，再返回访问兄弟节点。深度优先搜索通常使用递归来实现，也可以通过栈来手动模拟递归过程。在遍历过程中，一旦访问到一个未访问过的节点，就标记该节点为已访问，并继续深入访问其子节点。

        广度优先搜索则是从起始节点开始，一层一层地往外探索。先访问离起点最近的所有节点，再访问次近的节点，以此类推。这个过程，类似于树的层次遍历。广度优先搜索主要利用队列数据结构来实现：从根节点开始，将其放入队列中，然后从队列中取出节点并访问；接着，将该节点的所有未访问过的邻接节点放入队列，重复这一过程直到队列为空。

深度优先搜索算法

        我们首先使用深度优先搜索（DFS）算法来求解本题。DFS是一种递归算法，用于遍历或搜索树或图的数据结构。在本题中，我们可以将每个‘1’视为图中的一个节点，相邻的‘1’之间存在边。我们的目标是遍历所有与当前节点相连的陆地节点，并避免重复计数。使用DFS求解本题的主要步骤如下。

        1、初始化计数器。设置一个岛屿计数器，初始值为0。

        2、遍历网格。遍历整个二维网格的每一个元素，当遇到值为‘1’的元素时，进行以下操作。

        （1）增加岛屿计数器的值。

        （2）对该位置调用以下的DFS函数，以探索与之相连的所有陆地。

        （3）在DFS过程中，将访问过的陆地标记为其他值，以防止重复计数。

        3、DFS函数，功能如下。

        （1）输入一个坐标，检查该坐标是否在网格内且值为‘1’，如果不是则返回。

        （2）将当前位置标记为已访问（比如：改为‘2’）。

        （3）递归地对当前位置的上、下、左、右邻居进行DFS，确保只访问未标记的陆地。

        4、完成遍历：当整个网格遍历完成后，计数器的值即为岛屿总数。

        根据上面的算法步骤，我们可以得出下面的示例代码。

def dfs(grid, row, col):if row < 0 or col < 0 or row >= len(grid) or \col >= len(grid[0]) or grid[row][col] != '1':return# 标记为已访问grid[row][col] = '2'# 向下dfs(grid, row + 1, col)# 向上dfs(grid, row - 1, col)# 向右dfs(grid, row, col + 1)# 向左dfs(grid, row, col - 1)def island_count_by_dfs(grid):count = 0for row in range(len(grid)):for col in range(len(grid[0])):if grid[row][col] == '1':count += 1dfs(grid, row, col)return countgrid = [['1', '1', '0', '0', '0'],['1', '1', '0', '0', '0'],['0', '0', '1', '0', '0'],['0', '0', '0', '1', '1']
]
print(island_count_by_dfs(grid))

广度优先搜索算法

        接下来，我们使用广度优先搜索（BFS）算法来求解本题。BFS通过队列逐层探索二维网格地图，标记访问过的陆地，从而逐个发现并计数岛屿。使用BFS求解本题的主要步骤如下。

        1、初始化。设立一个队列用于BFS遍历，以及一个计数器来记录岛屿数量。

        2、遍历网格。遍历整个二维网格，对于每个元素，如果遇到值为‘1’的（表示陆地），进行以下操作。

        （1）增加岛屿计数器。

        （2）将此陆地坐标放入队列中，并将其标记为已访问（比如：改为‘2’）。

        （3）开始BFS，从当前坐标出发，探索所有相连的陆地。

        3、BFS过程，大致步骤如下。

        （1）从队列中取出一个坐标。

        （2）探索其上、下、左、右四个相邻坐标。

        （3）对于每个未访问的陆地邻居，将其标记为已访问，并加入队列。

        （4）重复上述过程，直到队列为空。

        根据上面的算法步骤，我们可以得出下面的示例代码。

from collections import dequedef bfs(grid, row, col):queue = deque([(row, col)])directions = [(0, 1), (0, -1), (1, 0), (-1, 0)]while queue:r, c = queue.popleft()for dr, dc in directions:new_r, new_c = r + dr, c + dcif 0 <= new_r < len(grid) and 0 <= new_c < len(grid[0]) \and grid[new_r][new_c] == '1':grid[new_r][new_c] = '2'queue.append((new_r, new_c))def island_count_by_bfs(grid):island_count = 0for row in range(len(grid)):for col in range(len(grid[0])):if grid[row][col] == '1':island_count += 1bfs(grid, row, col)return island_countgrid = [['1', '1', '0', '0', '0'],['1', '1', '0', '0', '0'],['0', '0', '1', '0', '0'],['0', '0', '0', '1', '1']
]
print(island_count_by_bfs(grid))

总结

        可以看到，无论是DFS还是BFS，时间复杂度均为O(M * N)，空间复杂度在最坏情况下为O(M)或O(N)，取决于地图的具体布局和岛屿的分布情况。其中，M是网格的行数，N是网格的列数。