代码随想录Day51 99. 岛屿数量，99. 岛屿数量，100. 岛屿的最大面积。

1.岛屿数量深搜

卡码网题目链接（ACM模式）(opens new window)

题目描述：

给定一个由 1（陆地）和 0（水）组成的矩阵，你需要计算岛屿的数量。岛屿由水平方向或垂直方向上相邻的陆地连接而成，并且四周都是水域。你可以假设矩阵外均被水包围。

输入描述：

第一行包含两个整数 N, M，表示矩阵的行数和列数。

后续 N 行，每行包含 M 个数字，数字为 1 或者 0。

输出描述：

输出一个整数，表示岛屿的数量。如果不存在岛屿，则输出 0。

输入示例：

4 5
1 1 0 0 0
1 1 0 0 0
0 0 1 0 0
0 0 0 1 1

输出示例：

3

提示信息

根据测试案例中所展示，岛屿数量共有 3 个，所以输出 3。

数据范围：

• 1 <= N, M <= 50

思路

注意题目中每座岛屿只能由水平方向和/或竖直方向上相邻的陆地连接形成。

也就是说斜角度链接是不算了， 例如示例二，是三个岛屿，如图：

这道题题目是 DFS，BFS，并查集，基础题目。

本题思路，是用遇到一个没有遍历过的节点陆地，计数器就加一，然后把该节点陆地所能遍历到的陆地都标记上。

在遇到标记过的陆地节点和海洋节点的时候直接跳过。 这样计数器就是最终岛屿的数量。

那么如何把节点陆地所能遍历到的陆地都标记上呢，就可以使用 DFS，BFS或者并查集。

深度优先搜索

使用dfs实现，如果对dfs不太了解的话，建议按照代码随想录的讲解顺序学习。

可能有疑惑，为什么 以上代码中的dfs函数，没有终止条件呢？ 感觉递归没有终止很危险。

其实终止条件 就写在了 调用dfs的地方，如果遇到不合法的方向，直接不会去调用dfs。

区别了，无疑就是版本一中 调用dfs 的条件判断 放在了 版本二 的 终止条件位置上。

版本一的写法是 ：下一个节点是否能合法已经判断完了，传进dfs函数的就是合法节点。

版本二的写法是：不管节点是否合法，上来就dfs，然后在终止条件的地方进行判断，不合法再return。

理论上来讲，版本一的效率更高一些，因为避免了 没有意义的递归调用，在调用dfs之前，就做合法性判断。 但从写法来说，可能版本二 更利于理解一些。（不过其实都差不太多）

很多同学看了同一道题目，都是dfs，写法却不一样，有时候有终止条件，有时候连终止条件都没有，其实这就是根本原因，两种写法而已。

public class Number_of_Islands_Depth_First_Search {public static int[][] dir ={{0,1},{1,0},{-1,0},{0,-1}};//二维数组，存储了深度优先搜索中可以探索的四个方向：右、下、左、上。public static void dfs(boolean[][] visited,int x,int y ,int [][]grid){//递归方法，用于执行深度优先搜索。boolean[][] visited 参数是一个与grid同样大小的二维数组，用来标记某个单元格是否已经被访问过。int x 和 int y 分别是当前单元格的行和列索引。int[][] grid 是输入的二维数组，表示地图，其中1表示陆地，0表示水域。for (int i = 0; i < 4; i++) {//对于当前单元格的每一个可能的相邻单元格（右、下、左、上），计算其坐标nextX和nextY。int nextX=x+dir[i][0];int nextY=y+dir[i][1];if(nextY<0||nextX<0||nextX>= grid.length||nextY>=grid[0].length)continue;//检查计算出的坐标是否在grid的边界内，并且该单元格是否未被访问过且值为1（陆地）。if(!visited[nextX][nextY]&&grid[nextX][nextY]==1){//如果一个相邻单元格满足上述条件，将其标记为已访问，并递归调用dfs方法探索该单元格。visited[nextX][nextY]=true;dfs(visited,nextX,nextY,grid);}}}public static void main(String[] args) {Scanner sc = new Scanner(System.in);//使用Scanner类从标准输入读取数据。int m= sc.nextInt();//首先读取两个整数m和n，分别代表地图的行数和列数。int n = sc.nextInt();int[][] grid = new int[m][n];//创建一个大小为m x n的二维数组grid，用于存储地图数据。for (int i = 0; i < m; i++) {//循环读取m x n个整数填充grid。for (int j = 0; j < n; j++) {grid[i][j]=sc.nextInt();}}boolean[][]visited =new boolean[m][n];//创建一个大小为m x n的布尔二维数组visited，初始化为false，表示所有单元格都未被访问。int ans = 0;//初始化一个整数ans用于存储岛屿的数量。for (int i = 0; i < m; i++) {//遍历grid中的每个单元格，对于每个值为1且未被访问的单元格，执行以下操作：将ans加1，表示找到一个新岛屿。将该单元格标记为已访问。调用dfs方法从该单元格开始搜索整个岛屿。for (int j = 0; j < n; j++) {if(!visited[i][j]&&grid[i][j]==1){ans++;visited[i][j]=true;dfs(visited,i,j,grid);}}}System.out.println(ans);}
}

• 时间复杂度：O(4 * m * n)，其中m和n分别是地图的行数和列数。
• 空间复杂度：O(m * n)，主要由visited数组和递归栈空间占用。

2.岛屿数量广搜

卡码网题目链接（ACM模式）(opens new window)

题目描述：

给定一个由 1（陆地）和 0（水）组成的矩阵，你需要计算岛屿的数量。岛屿由水平方向或垂直方向上相邻的陆地连接而成，并且四周都是水域。你可以假设矩阵外均被水包围。

输入描述：

第一行包含两个整数 N, M，表示矩阵的行数和列数。

后续 N 行，每行包含 M 个数字，数字为 1 或者 0。

输出描述：

输出一个整数，表示岛屿的数量。如果不存在岛屿，则输出 0。

输入示例：

4 5
1 1 0 0 0
1 1 0 0 0
0 0 1 0 0
0 0 0 1 1

输出示例：

3

提示信息

根据测试案例中所展示，岛屿数量共有 3 个，所以输出 3。

数据范围：

• 1 <= N, M <= 50

思路

注意题目中每座岛屿只能由水平方向和/或竖直方向上相邻的陆地连接形成。

也就是说斜角度链接是不算了， 例如示例二，是三个岛屿，如图：

这道题题目是 DFS，BFS，并查集，基础题目。

本题思路:遇到一个没有遍历过的节点陆地，计数器就加一，然后把该节点陆地所能遍历到的陆地都标记上。

再遇到标记过的陆地节点和海洋节点的时候直接跳过。 这样计数器就是最终岛屿的数量。

那么如果把节点陆地所能遍历到的陆地都标记上呢，就可以使用 DFS，BFS或者并查集。

广度优先搜索

如果不熟悉广搜，建议先看 广搜理论基础。

不少同学用广搜做这道题目的时候，超时了。 这里有一个广搜中很重要的细节：

根本原因是只要 加入队列就代表 走过，就需要标记，而不是从队列拿出来的时候再去标记走过。

很多同学可能感觉这有区别吗？

如果从队列拿出节点，再去标记这个节点走过，就会发生下图所示的结果，会导致很多节点重复加入队列。

超时写法 （从队列中取出节点再标记，注意代码注释的地方）

public class Number_of_Islands_Breadth_First_Search {static class pair {//static class pair 是一个内部类，用于存储坐标对。int first 和 int second 分别存储x和y坐标。构造函数 pair(int first, int second) 初始化坐标对。int first;int second;pair(int first, int second) {this.first = first;this.second = second;}}public static int[][] dir = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};//二维数组，存储了广度优先搜索中可以探索的四个方向：右、下、左、上。public static void bfs(int[][] grid, boolean[][] visited, int x, int y) {//方法，用于执行广度优先搜索。int[][] grid 是输入的二维数组，表示地图，其中1表示陆地，0表示水域。boolean[][] visited 参数是一个与grid同样大小的二维数组，用来标记某个单元格是否已经被访问过。int x 和 int y 分别是当前单元格的行和列索引。Queue<pair> queue = new LinkedList<pair>();//创建一个队列queue，用于存储待访问的坐标对。queue.add(new pair(x, y));//将起始坐标(x, y)添加到队列中，并标记为已访问。visited[x][y] = true;while (!queue.isEmpty()) {//当队列不为空时，执行以下操作：取出队列中的下一个坐标(curX, curY)。对于当前坐标的每一个可能的相邻单元格（右、下、左、上），计算其坐标nextX和nextY。如果计算出的坐标在grid的边界内，并且该单元格未被访问过且值为1（陆地），则将其添加到队列中，并标记为已访问。int curX = queue.peek().first;int curY = queue.poll().second;for (int i = 0; i < 4; i++) {int nextX = curX + dir[i][0];int nextY = curY + dir[i][1];if (nextX < 0 || nextX >= grid.length || nextY < 0 || nextY >= grid[0].length) {continue;}if (!visited[nextX][nextY] && grid[nextX][nextY] == 1) {queue.add(new pair(nextX, nextY));visited[nextX][nextY] = true;}}}}public static void main(String[] args) {Scanner sc = new Scanner(System.in);//使用Scanner类从标准输入读取数据。int m = sc.nextInt();//首先读取两个整数m和n，分别代表地图的行数和列数。int n = sc.nextInt();int[][] grid = new int[m][n];//创建一个大小为m x n的二维数组grid，用于存储地图数据。boolean[][] visited = new boolean[m][n];//创建一个大小为m x n的布尔二维数组visited，初始化为false，表示所有单元格都未被访问。int ans = 0;for (int i = 0; i < m; i++) {//循环读取m x n个整数填充grid。for (int j = 0; j < n; j++) {grid[i][j] = sc.nextInt();}}for (int i = 0; i < m; i++) {//初始化一个整数ans用于存储岛屿的数量。遍历grid中的每个单元格，对于每个值为1且未被访问的单元格，执行以下操作：将ans加1，表示找到一个新岛屿。调用bfs方法从该单元格开始搜索整个岛屿。for (int j = 0; j < n; j++) {if (!visited[i][j] && grid[i][j] == 1) {ans++;bfs(grid, visited, i, j);}}}System.out.println(ans);}
}

• 时间复杂度：O(4 * m * n)，其中m和n分别是地图的行数和列数。
• 空间复杂度：O(m * n)，主要由visited数组和队列空间占用。

3.岛屿的最大面积

卡码网题目链接（ACM模式）(opens new window)

题目描述

给定一个由 1（陆地）和 0（水）组成的矩阵，计算岛屿的最大面积。岛屿面积的计算方式为组成岛屿的陆地的总数。岛屿由水平方向或垂直方向上相邻的陆地连接而成，并且四周都是水域。你可以假设矩阵外均被水包围。

输入描述

第一行包含两个整数 N, M，表示矩阵的行数和列数。后续 N 行，每行包含 M 个数字，数字为 1 或者 0，表示岛屿的单元格。

输出描述

输出一个整数，表示岛屿的最大面积。如果不存在岛屿，则输出 0。

输入示例

4 5
1 1 0 0 0
1 1 0 0 0
0 0 1 0 0
0 0 0 1 1

输出示例

4

提示信息

样例输入中，岛屿的最大面积为 4。

数据范围：

• 1 <= M, N <= 50。

思路

注意题目中每座岛屿只能由水平方向和/或竖直方向上相邻的陆地连接形成。

也就是说斜角度链接是不算了， 例如示例二，是三个岛屿，如图：

这道题目也是 dfs bfs基础类题目，就是搜索每个岛屿上“1”的数量，然后取一个最大的。

本题思路上比较简单，难点其实都是 dfs 和 bfs的理论基础，关于理论基础我在这里都有详细讲解 ：

• DFS理论基础(opens new window)
• BFS理论基础(opens new window)

DFS

很多同学写dfs其实也是凭感觉来的，有的时候dfs函数中写终止条件才能过，有的时候 dfs函数不写终止添加也能过！

这里其实涉及到dfs的两种写法。

写法一，dfs只处理下一个节点，即在主函数遇到岛屿就计数为1，dfs处理接下来的相邻陆地。

写法二，dfs处理当前节点，即在主函数遇到岛屿就计数为0，dfs处理接下来的全部陆地

两种写法，版本一，在主函数遇到陆地就计数为1，接下来的相邻陆地都在dfs中计算。

版本二 在主函数遇到陆地 计数为0，也就是不计数，陆地数量都去dfs里做计算。

这也是为什么大家看了很多 dfs的写法 ，发现写法怎么都不一样呢？ 其实这就是根本原因。

BFS

关于广度优先搜索，如果大家还不了解的话，看这里：广度优先搜索精讲

public class Maximum_Area_of_an_Island {static class Pair {//static class Pair 是一个辅助类，用于存储坐标对。int x 和 int y 分别存储横坐标和纵坐标。构造函数 Pair(int x, int y) 用于创建一个新的坐标对实例。int x;int y;Pair(int x, int y) {this.x = x;this.y = y;}}public static int[][] directions = {{0, 1}, {1, 0}, {-1, 0}, {0, -1}}; // 定义了四个方向的移动，分别对应右、下、左、上。public static void dfs(int[][] grid, boolean[][] visited, int x, int y, int[] area) {//输入的二维数组，表示地图，其中1表示陆地，0表示水域。boolean[][] visited 是一个与grid同样大小的布尔数组，用来标记某个单元格是否已经被访问过。int x 和 int y 是当前单元格的坐标。int[] area 是一个整数数组，用于计算当前岛屿的面积。if (x < 0 || x >= grid.length || y < 0 || y >= grid[0].length || visited[x][y] || grid[x][y] == 0) {return;//检查当前坐标是否越界、是否已被访问或是否是水域。如果是，则返回。}visited[x][y] = true;//如果当前坐标是陆地（grid[x][y] == 1），则将其标记为已访问，并增加岛屿面积。area[0]++;//然后，方法递归地对当前坐标的所有四个方向进行搜索，以找到整个岛屿。for (int[] direction : directions) {dfs(grid, visited, x + direction[0], y + direction[1], area);}}public static int maxAreaOfIsland(int[][] grid) {if (grid == null || grid.length == 0) {//检查输入的网格是否为空。return 0;}//创建一个布尔数组 visited 来跟踪访问过的单元格。boolean[][] visited = new boolean[grid.length][grid[0].length];int maxArea = 0;//初始化 maxArea 变量为0，用于存储最大岛屿面积。for (int i = 0; i < grid.length; i++) {//遍历网格中的每个单元格，如果发现未访问的陆地（grid[i][j] == 1），则调用 dfs 方法计算该岛屿的面积，并更新 maxArea。for (int j = 0; j < grid[0].length; j++) {if (grid[i][j] == 1 && !visited[i][j]) {int[] area = new int[1]; // 用于计算当前岛屿的面积dfs(grid, visited, i, j, area);maxArea = Math.max(maxArea, area[0]);}}}return maxArea;}public static void main(String[] args) {Scanner scanner = new Scanner(System.in);//使用 Scanner 类从标准输入读取数据。System.out.println("Enter the number of rows and columns:");int m = scanner.nextInt();//首先读取两个整数 m 和 n，分别代表地图的行数和列数。int n = scanner.nextInt();int[][] grid = new int[m][n];//创建一个大小为 m x n 的二维数组 grid，用于存储地图数据。System.out.println("Enter the grid values:");for (int i = 0; i < m; i++) {//循环读取 m x n 个整数填充 grid。for (int j = 0; j < n; j++) {//调用 maxAreaOfIsland 方法计算最大岛屿面积，并输出结果。grid[i][j] = scanner.nextInt();}}int maxArea = maxAreaOfIsland(grid);System.out.println("Maximum area of an island is: " + maxArea);}
}

• 时间复杂度：O(m * n)，其中m和n分别是地图的行数和列数。
• 空间复杂度：O(m * n)，主要由visited数组和递归栈空间（或非递归DFS中的队列或栈）占用。