• 标签(题目类型)：深度优先搜索（DFS）、广度优先搜索（BFS）、并查集（Union Find）

题目描述

给定一个二维字符网格 map，'1' 表示陆地，'0' 表示水域。网格中的每个'1'都被视为一个岛屿的一部分，被水域包围的'1'（水平或垂直四个方向）形成岛屿。找出网格中岛屿的数量。

原题：LeetCode 200. 岛屿数量

思路及实现

方式一：深度优先搜索（DFS）

思路

使用深度优先搜索（DFS）遍历每个单元格，若遇到陆地’1’，则以该点作为起始点开始DFS，将与其相连的所有陆地都标记为已访问（例如，更改为’0’）。每次DFS表示遍历了一个完整的岛屿，岛屿数量加一。

代码实现

Java版本

java">public class Solution {private void dfs(char[][] grid, int i, int j) {int m = grid.length;int n = grid[0].length;// 判断边界条件和是否为陆地if (i < 0 || i >= m || j < 0 || j >= n || grid[i][j] != '1') {return;}// 标记为已访问（水域）grid[i][j] = '0';// 递归访问上下左右四个方向的相邻陆地dfs(grid, i - 1, j); // 上dfs(grid, i + 1, j); // 下dfs(grid, i, j - 1); // 左dfs(grid, i, j + 1); // 右}public int numIslands(char[][] grid) {if (grid == null || grid.length == 0) {return 0;}int m = grid.length;int n = grid[0].length;int count = 0;for (int i = 0; i < m; i++) {for (int j = 0; j < n; j++) {if (grid[i][j] == '1') {count++;dfs(grid, i, j);}}}return count;}
}

说明：Java版本使用递归的方式实现了DFS，并通过将已访问的陆地标记为’0’来避免重复计数。

C语言版本

#include <stdbool.h>void dfs(char** grid, int gridSize, int* gridColSize, int i, int j) {if (i < 0 || i >= gridSize || j < 0 || j >= gridColSize[0] || grid[i][j] == '0') {return;}grid[i][j] = '0'; // 标记为已访问dfs(grid, gridSize, gridColSize, i - 1, j); // 上dfs(grid, gridSize, gridColSize, i + 1, j); // 下dfs(grid, gridSize, gridColSize, i, j - 1); // 左dfs(grid, gridSize, gridColSize, i, j + 1); // 右
}int numIslands(char** grid, int gridSize, int* gridColSize){if (grid == NULL || gridSize == 0 || gridColSize[0] == 0) {return 0;}int count = 0;for (int i = 0; i < gridSize; i++) {for (int j = 0; j < gridColSize[0]; j++) {if (grid[i][j] == '1') {count++;dfs(grid, gridSize, gridColSize, i, j);}}}return count;
}

说明：C语言版本同样使用DFS，但需要注意二维数组的传递和边界条件的判断。

Python3版本

class Solution:def dfs(self, grid, i, j):if not 0 <= i < len(grid) or not 0 <= j < len(grid[0]) or grid[i][j] != '1':returngrid[i][j] = '0'  # 标记为已访问# 递归访问上下左右四个方向的相邻陆地self.dfs(grid, i - 1, j)  # 上self.dfs(grid, i + 1, j)  # 下self.dfs(grid, i, j - 1)  # 左self.dfs(grid, i, j + 1)  # 右def numIslands(self, grid: List[List[str]]) -> int:if not grid:return 0rows, cols = len(grid), len(grid[0])count = 0for i in range(rows):for j in range(cols):if grid[i][j] == '1':count += 1self.dfs(grid, i, j)return count

说明：Python3版本同样使用了DFS，但将DFS定义为了类方法，并处理了二维列表的边界条件和访问标记。

Golang版本

func dfs(grid [][]byte, i, j int) {rows, cols := len(grid), len(grid[0])if i < 0 || i >= rows || j < 0 || j >= cols || grid[i][j] != '1' {return}grid[i][j] = '0' // 标记为已访问// 递归访问上下左右四个方向的相邻陆地dfs(grid, i-1, j) // 上dfs(grid, i+1, j) // 下dfs(grid, i, j-1) // 左dfs(grid, i, j+1) // 右
}func numIslands(grid [][]byte) int {if len(grid) == 0 {return 0}rows, cols := len(grid), len(grid[0])count := 0for i := 0; i < rows; i++ {for j := 0; j < cols; j++ {if grid[i][j] == '1' {count++dfs(grid, i, j)}}}return count
}

说明：Golang版本同样使用了DFS算法，但注意在Go中二维数组（切片）的传递和边界条件判断。

复杂度分析

• 时间复杂度：O(mn)，其中m和n分别是网格的行数和列数。因为我们需要遍历整个网格一次，并且在每个陆地上都执行DFS操作，DFS操作的时间复杂度取决于与当前陆地相连的其他陆地的数量，但最坏情况下会遍历完整个网格，因此总的时间复杂度是O(mn)。
• 空间复杂度：O(mn)（DFS栈空间）。在最坏的情况下，整个网格都是陆地，并且所有陆地都相互连接，此时DFS的递归调用栈会达到最大深度，即网格的面积mn。然而，在平均情况下，空间复杂度会远小于O(mn)，因为大多数DFS调用都会在遇到水域时返回。

方式二： 使用广度优先搜索（BFS）

思路

与DFS类似，BFS也通过遍历网格来寻找岛屿。但BFS通常使用队列来存储待访问的节点（在这里是网格中的位置）。当一个陆地（‘1’）被访问时，我们将其标记为已访问（如’0’），并将其四个相邻的陆地（如果存在）加入队列中。我们继续从队列中取出节点，直到队列为空，这意味着我们已经探索了一个完整的岛屿。然后，我们重复这个过程，直到所有的陆地都被访问过。

代码实现

Java实现

java">import java.util.LinkedList;
import java.util.Queue;public class Solution {public int numIslands(char[][] grid) {if (grid == null || grid.length == 0) return 0;int count = 0;int m = grid.length;int n = grid[0].length;for (int i = 0; i < m; i++) {for (int j = 0; j < n; j++) {if (grid[i][j] == '1') {count++;bfs(grid, i, j);}}}return count;}private void bfs(char[][] grid, int row, int col) {int m = grid.length;int n = grid[0].length;// 定义上下左右四个方向的偏移量int[] dx = {-1, 1, 0, 0};int[] dy = {0, 0, -1, 1};// 使用队列存储待访问的节点Queue<int[]> queue = new LinkedList<>();queue.offer(new int[]{row, col});// 标记当前节点为已访问grid[row][col] = '0';while (!queue.isEmpty()) {int[] curr = queue.poll();int x = curr[0];int y = curr[1];// 遍历四个方向for (int i = 0; i < 4; i++) {int nx = x + dx[i];int ny = y + dy[i];// 检查是否越界和是否为陆地且未访问if (nx >= 0 && nx < m && ny >= 0 && ny < n && grid[nx][ny] == '1') {// 标记为已访问并加入队列grid[nx][ny] = '0';queue.offer(new int[]{nx, ny});}}}}
}

C++实现

#include <queue>
#include <vector>using namespace std;void bfs(vector<vector<char>>& grid, int i, int j) {int m = grid.size();int n = grid[0].size();// 定义上下左右四个方向的偏移量vector<int> dx = {-1, 1, 0, 0};vector<int> dy = {0, 0, -1, 1};// 使用队列存储待访问的节点queue<pair<int, int>> q;q.push({i, j});// 标记当前节点为已访问grid[i][j] = '0';while (!q.empty()) {auto curr = q.front();q.pop();int x = curr.first;int y = curr.second;// 遍历四个方向for (int k = 0; k < 4; k++) {int nx = x + dx[k];int ny = y + dy[k];// 检查是否越界和是否为陆地且未访问if (nx >= 0 && nx < m && ny >= 0 && ny < n && grid[nx][ny] == '1') {// 标记为已访问并加入队列grid[nx][ny] = '0';q.push({nx, ny});}}}
}int numIslands(vector<vector<char>>& grid) {if (grid.empty()) return 0;int m = grid.size();int n = grid[0].size();int count = 0;for (int i = 0; i < m; i++) {for (int j = 0; j < n; j++) {if (grid[i][j] == '1') {count++;bfs(grid, i, j);}}}return count;
}

Python3实现

from collections import dequedef bfs(grid, row, col):m, n = len(grid), len(grid[0])directions = [(0, 1), (0, -1), (1, 0), (-1, 0)]  # 右，左，下，上queue = deque([(row, col)])grid[row][col] = 0  # 标记为已访问while queue:x, y = queue.popleft()for dx, dy in directions:nx, ny = x + dx, y + dyif 0 <= nx < m and 0 <= ny < n and grid[nx][ny] == '1':grid[nx][ny] = 0  # 标记为已访问queue.append((nx, ny))def numIslands(grid):if not grid:return 0m, n = len(grid), len(grid[0])count = 0for i in range(m):for j in range(n):if grid[i][j] == '1':count += 1bfs(grid, i, j)return count

Go实现

package mainimport ("container/list"
)type Point struct {X, Y int
}func bfs(grid [][]byte, row, col int) {m, n := len(grid), len(grid[0])directions := [][]int{{-1, 0}, {1, 0}, {0, -1}, {0, 1}} // 上，下，左，右queue := list.New()queue.PushBack(Point{row, col})grid[row][col] = '0' // 标记为已访问for queue.Len() > 0 {curr := queue.Front().Value.(Point)queue.Remove(queue.Front())for _, dir := range directions {nx, ny := curr.X+dir[0], curr.

总结

方式	优点	缺点	时间复杂度	空间复杂度
DFS	实现简单，容易理解	在最坏情况下，空间复杂度较高	O(mn)	O(mn)（DFS栈空间）

相似题目

相似题目	难度	链接
LeetCode 695. 岛屿的最大面积	中等	LeetCode链接
LeetCode 130. 被围绕的区域	中等	LeetCode链接
[LeetCode 1254. 统计封闭岛屿的数目