请选择 进入手机版 | 继续访问电脑版

[C 语言] C++或Go求矩阵里的岛屿的数目 详解

[复制链接]
查看76 | 回复10 | 2021-9-12 18:48:50 | 显示全部楼层 |阅读模式
目次

给你一个由 ‘1'(陆地)和 ‘0'(水)构成 的的二维网格,请你计算网格中岛屿的数量 。

岛屿总是被水包围,并且每座岛屿只能由程度 方向和/或竖直方向上相邻的陆地毗连 形成。此外,你可以假设该网格的四条边均被水包围。

示例 1:

输入:

  1. grid = [
  2. [“1”,“1”,“1”,“1”,“0”],
  3. [“1”,“1”,“0”,“1”,“0”],
  4. [“1”,“1”,“0”,“0”,“0”],
  5. [“0”,“0”,“0”,“0”,“0”]
  6. ]
复制代码

输出:

  1. 1
复制代码

示例 2:

输入:

  1. grid = [
  2. [“1”,“1”,“0”,“0”,“0”],
  3. [“1”,“1”,“0”,“0”,“0”],
  4. [“0”,“0”,“1”,“0”,“0”],
  5. [“0”,“0”,“0”,“1”,“1”]
  6. ]
复制代码

输出:

  1. 3
复制代码

提示:

  1. m == grid.length
  2. n == grid[i].length
  3. 1 <= m, n <= 300
  4. grid[i][j] 的值为 ‘0' 或 ‘1'
复制代码

此孤岛标题 ,可以通过DFS算法办理 ,详细 如下:

1、C++实现

//island.cpp

  1. #include <iostream>
  2. #include <algorithm>
  3. #include <string>
  4. #include <vector>
  5. using namespace std;
  6. //判断坐标(r,c)是否存在网络中
  7. bool inArea(vector<vector<char>>& grid, int r, int c) {
  8. bool bRow = (r >= 0) && (r < (int)grid.size());
  9. bool bCol = (c >= 0) && (c < (int)grid[0].size());
  10. return bRow && bCol;
  11. }
  12. //void dfs(int[][] grid, int r, int c) {
  13. void dfs(vector<vector<char>>& grid, int r,int c){
  14. //判断base case
  15. //如果坐标(r,c)超出了网格范围,则直接返回
  16. if (!inArea(grid,r,c)) {
  17. return;
  18. }
  19. //如果不是岛屿,则直接返回
  20. if (grid[r][c] != '1') {
  21. return;
  22. }
  23. //将原来的"1"改成"0"
  24. grid[r][c] = '2';
  25. //访问上、下、左、右四个相邻结点
  26. dfs(grid, r - 1, c);
  27. dfs(grid, r + 1, c);
  28. dfs(grid, r , c-1);
  29. dfs(grid, r , c+1);
  30. }
  31. //求岛屿的个数
  32. //时间复杂度:O(MN)O(MN),其中 MM 和 NN 分别为行数和列数。
  33. //空间复杂度:O(MN)O(MN),在最坏情况下,整个网格均为陆地,深度优先搜索的深度达到MN。
  34. //
  35. int numIslands(vector<vector<char>>& grid){
  36. int r = grid.size();
  37. if (!r)
  38. return 0;
  39. int c = grid[0].size();
  40. int num = 0;
  41. for (int i = 0; i < r; i++) {
  42. for (int j = 0; j < c; j++) {
  43. if (grid[i][j] == '1') {
  44. ++num;
  45. dfs(grid, i, j);
  46. }
  47. }
  48. }
  49. return num;
  50. }
  51. int main(){
  52. //岛屿
  53. // 1 1 1
  54. // 0 1 0
  55. // 1 0 0
  56. // 1 0 1
  57. vector<char> row1;
  58. row1.push_back('1');
  59. row1.push_back('1');
  60. row1.push_back('1');
  61. vector<char> row2;
  62. row2.push_back('0');
  63. row2.push_back('1');
  64. row2.push_back('0');
  65. vector<char> row3;
  66. row3.push_back('1');
  67. row3.push_back('0');
  68. row3.push_back('0');
  69. vector<char> row4;
  70. row4.push_back('1');
  71. row4.push_back('0');
  72. row4.push_back('1');
  73. vector<vector<char>> grid;
  74. grid.push_back(row1);
  75. grid.push_back(row2);
  76. grid.push_back(row3);
  77. grid.push_back(row4);
  78. int numLands = numIslands(grid);
  79. cout << "numLands= " << numLands << endl;
  80. system("pause");
  81. return 0;
  82. }
复制代码

效果 如下:

C++或Go求矩阵里的岛屿的数目
详解

图(1) 孤岛的个数

2、go语言实现

//island.go

  1. package main
  2. import "fmt"
  3. func numIslands(grid [][]byte) int {
  4. nums := 0
  5. for i:=0; i<len(grid); i++ {
  6. for j:=0; j<len(grid[0]); j++ {
  7. if grid[i][j] == '1' {
  8. DFS(&grid,i,j)
  9. nums++
  10. }
  11. }
  12. }
  13. return nums
  14. }
  15. func DFS(grid *[][]byte, i int, j int) {
  16. var (
  17. row = len(*grid)
  18. col = len((*grid)[0])
  19. )
  20. if i<0 || i>=row || j<0 || j>= col {
  21. return
  22. }
  23. if (*grid)[i][j] == '1' {
  24. (*grid)[i][j] = '2'
  25. DFS(grid,i-1,j)
  26. DFS(grid,i+1,j)
  27. DFS(grid,i,j-1)
  28. DFS(grid,i,j+1)
  29. }
  30. }
  31. func main() {
  32. var grid = make([][]byte, 4)
  33. grid[0] = []byte{'1','1','1'}
  34. grid[1] = []byte{'0','1','0'}
  35. grid[2] = []byte{'1','0','0'}
  36. grid[3] = []byte{'1','0','1'}
  37. res := numIslands(grid)
  38. fmt.Println("numlands=",res)
  39. }
复制代码

效果 如下:

C++或Go求矩阵里的岛屿的数目
详解

图(2) go语言实现,求岛屿的个数

参考文献

泉源 :力扣(LeetCode)

总结

本篇文章就到这里了,盼望 可以或许 给你带来帮助,也盼望 您可以或许 多多关注脚本之家的更多内容!


免责声明:如果侵犯了您的权益,请联系站长,我们会及时删除侵权内容,谢谢合作!

本帖子中包含更多资源

您需要 登录 才可以下载或查看,没有帐号?立即注册

x
回复

使用道具 举报

avatar m4659631 | 2021-9-17 02:32:32 | 显示全部楼层
admin楼主今年多大了?
回复

使用道具 举报

admin楼主,我告诉你一个你不知道的的秘密,有一个牛逼的网站,运动刷步数还是免费刷的,QQ和微信都可以刷,特别好用。访问地址:http://yd.mxswl.com 猫先森网络
回复

使用道具 举报

avatar 陈嘉凯 | 2021-10-3 01:48:00 | 显示全部楼层
支持一下,下面的保持队形!
回复

使用道具 举报

avatar V刘晨曦 | 2021-10-3 08:17:03 | 显示全部楼层
admin楼主,我告诉你一个你不知道的的秘密,有一个牛逼的网站,他卖的服务器是永久的,我们的网站用 服务器都是在这家买的,你可以去试试。访问地址:http://fwq.mxswl.com
回复

使用道具 举报

avatar 慧眼识英雄1 | 2021-10-4 03:23:53 | 显示全部楼层
admin楼主,我告诉你一个你不知道的的秘密,有一个牛逼的源码论坛他的站点都是商业源码,还是免费下载的那种!特别好用。访问地址:http://www.mxswl.com 猫先森网络
回复

使用道具 举报

avatar 姆班他姑店 | 2021-10-4 09:45:03 | 显示全部楼层
很多天不上线,一上线就看到这么给力的帖子!
回复

使用道具 举报

avatar 墙和鸡蛋 | 2021-10-16 01:18:58 | 显示全部楼层
今天是个特别的日子,值得纪念!
回复

使用道具 举报

楼上的真不讲道理!
回复

使用道具 举报

脑残片admin楼主今天吃了么?
回复

使用道具 举报

您需要登录后才可以回帖 登录 | 立即注册

本版积分规则