200. 岛屿数量

🟠   🔖  深度优先搜索 广度优先搜索 并查集 数组 矩阵  🔗 力扣 LeetCode

题目

Given an m x n 2D binary grid grid which represents a map of '1's (land) and '0's (water), return the number of islands.

An island is surrounded by water and is formed by connecting adjacent lands horizontally or vertically. You may assume all four edges of the grid are all surrounded by water.

Example 1:

Input: grid = [

["1","1","1","1","0"],

["1","1","0","1","0"],

["1","1","0","0","0"],

["0","0","0","0","0"]

]

Output: 1

Example 2:

Input: grid = [

["1","1","0","0","0"],

["1","1","0","0","0"],

["0","0","1","0","0"],

["0","0","0","1","1"]

]

Output: 3

Constraints:

• m == grid.length
• n == grid[i].length
• 1 <= m, n <= 300
• grid[i][j] is '0' or '1'.

题目大意

给你一个由 '1'（陆地）和 '0'（水）组成的的二维网格，请你计算网格中岛屿的数量。

岛屿总是被水包围，并且每座岛屿只能由水平方向和/或竖直方向上相邻的陆地连接形成。

此外，你可以假设该网格的四条边均被水包围。

解题思路

遍历整个网格，并在每次找到一个陆地单元时，使用深度优先搜索（DFS）或广度优先搜索（BFS）来遍历所有相连的陆地单元，从而将整个岛屿标记为已访问。

1. 遍历网格：遍历每一个单元格，如果当前单元格是 '1'（陆地），则找到一个新的岛屿，计数器加一。
2. 标记已访问：使用 DFS 从当前单元格开始，标记所有连通的陆地单元为 '0'（水），表示它们已被访问。
3. 继续遍历：继续遍历剩余的单元格，直到整个网格被检查完。

复杂度分析

• 时间复杂度：O(m * n)，其中 m 是网格的行数，n 是网格的列数，每个格子最多会被访问一次。
• 空间复杂度：O(m * n)，最坏情况下，递归的深度可能达到 m * n，因此递归调用栈的空间复杂度为 O(m * n)

代码

/**
 * @param {character[][]} grid
 * @return {number}
 */
var numIslands = function (grid) {
	let res = 0;
	const m = grid.length,
		n = grid[0].length;

	// 从 (i, j) 开始，将与之相邻的陆地都变成海水
	const dfs = (grid, i, j) => {
		// 超出索引边界
		if (i < 0 || j < 0 || i >= m || j >= n) {
			return;
		}
		// (i, j) 已经是海水了
		if (grid[i][j] == '0') {
			return;
		}
		// 将 (i, j) 变成海水
		grid[i][j] = '0';
		// 淹没上下左右的陆地
		dfs(grid, i - 1, j); // 上
		dfs(grid, i + 1, j); // 下
		dfs(grid, i, j - 1); // 左
		dfs(grid, i, j + 1); // 右
	};

	// 遍历 grid
	for (let i = 0; i < m; i++) {
		for (let j = 0; j < n; j++) {
			if (grid[i][j] == '1') {
				// 每发现一个岛屿，岛屿数量加一
				res++;
				// 然后使用 DFS 将岛屿淹了
				dfs(grid, i, j);
			}
		}
	}

	return res;
};

相关题目

题号	标题	题解	标签	难度
130	被围绕的区域	[✓]	深度优先搜索 广度优先搜索 并查集 2+
286	墙与门 🔒		广度优先搜索 数组 矩阵
305	岛屿数量 II 🔒		并查集 数组 哈希表
323	无向图中连通分量的数目 🔒		深度优先搜索 广度优先搜索 并查集 1+
419	棋盘上的战舰		深度优先搜索 数组 矩阵
694	不同岛屿的数量 🔒		深度优先搜索 广度优先搜索 并查集 2+
695	岛屿的最大面积	[✓]	深度优先搜索 广度优先搜索 并查集 2+
1905	统计子岛屿		深度优先搜索 广度优先搜索 并查集 2+
1992	找到所有的农场组		深度优先搜索 广度优先搜索 数组 1+
2316	统计无向图中无法互相到达点对数		深度优先搜索 广度优先搜索 并查集 1+
2658	网格图中鱼的最大数目		深度优先搜索 广度优先搜索 并查集 2+