51、图论-岛屿数量

思路：

该问题要求在一个由 '1'（表示陆地）和 '0'（表示水）组成的二维网格中，计算岛屿的数量。岛屿被水包围，并且通过水平或垂直连接相邻的陆地可以形成。这个问题的核心是识别并计数网格中相连的陆地块。

方法 numIslands

1. 初始检查：

   • 首先检查输入的二维数组 m 是否为空或格式不正确（例如行或列为0）。如果是，返回0表示没有岛屿。

2. 定义变量：

   • N 表示网格的行数。
   • M 表示网格的列数。
   • res 用来记录岛屿的数量，初始化为0。

3. 遍历网格：

   • 使用双重循环遍历每个单元格。外循环遍历行，内循环遍历列。

4. 检查陆地并启动感染过程：

   • 如果当前单元格的值是 '1'，则表示找到了一个新岛屿，岛屿计数 res 增加1。
   • 调用 infect 方法来“感染”相邻的陆地区域，将其标记为已访问。

5. 返回岛屿数量：

   • 遍历完成后，返回总的岛屿数量 res。

方法 infect

这是一个递归方法，用于标记和访问与当前单元格相连的所有陆地单元格，以防止它们被重复计数：

1. 边界和终止条件：

   • 检查当前坐标 (i, j) 是否超出网格边界或当前单元格是否不是 '1'。如果是，返回，不做任何操作。

2. 标记当前单元格：

   • 将当前单元格的值从 '1' 修改为 '2'，表示这块陆地已经被访问过，以避免重复计数。

3. 递归感染相邻的陆地：

   • 递归调用 infect 方法分别向上、下、左、右四个方向探索，寻找并标记所有相连的陆地。

总结

这个解决方案通过DFS（深度优先搜索）来识别和计数所有的岛屿。每当找到一个未被访问的陆地单元格，就通过递归“感染”过程标记所有与之相连的陆地单元格，防止它们在后续的遍历中被重复计数。这种方法简单高效地解决了岛屿计数问题。

代码如下：

public static int numIslands(char[][] m) {
		if (m == null || m.length == 0 || m[0] == null || m[0].length == 0) {
			return 0;
		}
		int N = m.length;
		int M = m[0].length;
		int res = 0;
		for (int i = 0; i < N; i++) {
			for (int j = 0; j < M; j++) {
				if (m[i][j] == '1') {
					res++;
					infect(m, i, j, N, M);
				}
			}
		}
		return res;
	}

	public static void infect(char[][] m, int i, int j, int N, int M) {
		if (i < 0 || i >= N || j < 0 || j >= M || m[i][j] != '1') {
			return;
		}
		m[i][j] = '2';
		infect(m, i + 1, j, N, M);
		infect(m, i - 1, j, N, M);
		infect(m, i, j + 1, N, M);
		infect(m, i, j - 1, N, M);
	}