免费自建网站工具,如何开发wordpress子主题,网站建设及照片使用保密协议,电商网站建设源代码1.岛屿数量深搜
卡码网题目链接#xff08;ACM模式#xff09;(opens new window)
题目描述#xff1a;
给定一个由 1#xff08;陆地#xff09;和 0#xff08;水#xff09;组成的矩阵#xff0c;你需要计算岛屿的数量。岛屿由水平方向或垂直方向上相邻的陆地连接…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
思路
注意题目中每座岛屿只能由水平方向和/或竖直方向上相邻的陆地连接形成。
也就是说斜角度链接是不算了 例如示例二是三个岛屿如图 这道题题目是 DFSBFS并查集基础题目。
本题思路是用遇到一个没有遍历过的节点陆地计数器就加一然后把该节点陆地所能遍历到的陆地都标记上。
在遇到标记过的陆地节点和海洋节点的时候直接跳过。 这样计数器就是最终岛屿的数量。
那么如何把节点陆地所能遍历到的陆地都标记上呢就可以使用 DFSBFS或者并查集。
深度优先搜索
使用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 nextXxdir[i][0];int nextYydir[i][1];if(nextY0||nextX0||nextX grid.length||nextYgrid[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
思路
注意题目中每座岛屿只能由水平方向和/或竖直方向上相邻的陆地连接形成。
也就是说斜角度链接是不算了 例如示例二是三个岛屿如图 这道题题目是 DFSBFS并查集基础题目。
本题思路:遇到一个没有遍历过的节点陆地计数器就加一然后把该节点陆地所能遍历到的陆地都标记上。
再遇到标记过的陆地节点和海洋节点的时候直接跳过。 这样计数器就是最终岛屿的数量。
那么如果把节点陆地所能遍历到的陆地都标记上呢就可以使用 DFSBFS或者并查集。
广度优先搜索
如果不熟悉广搜建议先看 广搜理论基础。
不少同学用广搜做这道题目的时候超时了。 这里有一个广搜中很重要的细节
根本原因是只要 加入队列就代表 走过就需要标记而不是从队列拿出来的时候再去标记走过。
很多同学可能感觉这有区别吗
如果从队列拿出节点再去标记这个节点走过就会发生下图所示的结果会导致很多节点重复加入队列。 超时写法 从队列中取出节点再标记注意代码注释的地方
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 分别是当前单元格的行和列索引。Queuepair queue new LinkedListpair();//创建一个队列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只处理下一个节点即在主函数遇到岛屿就计数为1dfs处理接下来的相邻陆地。
写法二dfs处理当前节点即在主函数遇到岛屿就计数为0dfs处理接下来的全部陆地
两种写法版本一在主函数遇到陆地就计数为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中的队列或栈占用。
