📝个人主页：五敷有你      

 🔥系列专栏：算法分析与设计

⛺️稳中求进，晒太阳

题目

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

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

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

示例

示例 1：

输入：grid = [["1","1","1","1","0"],["1","1","0","1","0"],["1","1","0","0","0"],["0","0","0","0","0"]]
输出：1

示例 2：

输入：grid = [["1","1","0","0","0"],["1","1","0","0","0"],["0","0","1","0","0"],["0","0","0","1","1"]]
输出：3

思路.

• DFS是一种有序的搜索算法，它沿着一条路径尽可能地往深处搜索，直到无法继续为止，然后再回溯到前面的节点。
• 深度优先搜索适用于寻找路径、判断图的连通性、拓扑排序等问题。

        在算法实现中，可以使用递归或栈来实现深度优先搜索。递归是DFS的一种自然表达方式，但在实践中可能会导致栈溢出。另一种方法是使用显式的栈来模拟递归过程，这样可以避免栈溢出的问题，并允许更大规模的数据处理。

算法分析与设计

1. 定义了一个名为 numIslands 的函数，该函数接受一个二维字符数组 grid 作为输入，并返回岛屿的数量。
2. 在 numIslands 函数中，首先检查输入的 grid 是否为空或者长度为0，若是，则直接返回岛屿数量为0。
3. 获取二维数组 grid 的行数 nr 和列数 nc。
4. 使用两个嵌套的循环遍历整个二维数组 grid。在每个位置 (r, c) 上，检查当前位置是否为陆地（值为 '1'）。
5. 若当前位置为陆地，则将岛屿数量 num_islands 加1，并调用 dfs 函数进行深度优先搜索以标记与当前陆地相连的所有陆地。
6. dfs 函数用于标记相邻的陆地。首先，检查当前位置 (r, c) 是否在网格范围内以及是否为陆地。如果不是，则直接返回。
7. 将当前位置标记为已访问（将其值设为 '0'），然后递归调用 dfs 函数来标记上、下、左、右四个方向的相邻陆地。
8. 当所有与当前陆地相连的陆地都被标记为已访问后，dfs 函数递归返回。
9. 主循环继续执行，直到遍历完整个二维数组 grid。
10. 最后，返回岛屿数量 num_islands。

代码实现

class Solution {public int numIslands(char[][] grid) {if (grid == null || grid.length == 0) {return 0;}int nr = grid.length;int nc = grid[0].length;int num_islands = 0;for (int r = 0; r < nr; ++r) {for (int c = 0; c < nc; ++c) {if (grid[r][c] == '1') {++num_islands;dfs(grid, r, c);}}}return num_islands;}void dfs(char[][] grid, int r, int c) {int nr = grid.length;int nc = grid[0].length;if (r < 0 || c < 0 || r >= nr || c >= nc || grid[r][c] == '0') {return;}grid[r][c] = '0';dfs(grid, r - 1, c);dfs(grid, r + 1, c);dfs(grid, r, c - 1);dfs(grid, r, c + 1);}}

运行结果