怎么用C++或Go求矩阵里的岛屿的数量

本篇内容介绍了"怎么用C++或Go求矩阵里的岛屿的数量"的有关知识，在实际案例的操作过程中，不少人都会遇到这样的困境，接下来就让小编带领大家学习一下如何处理这些情况吧！希望大家仔细阅读，能够学有所成！

目录

• 1、C++实现

• 2、go语言实现

  
  

给你一个由 '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

提示：

m == grid.length
n == grid[i].length
1 <= m, n <= 300
grid[i][j] 的值为 '0' 或 '1'

此孤岛问题，可以通过DFS算法解决，具体如下：

1、C++实现

//island.cpp

#include #include #include #include using namespace std;//判断坐标(r,c)是否存在网络中bool inArea(vector>& grid, int r, int c) {        bool bRow = (r >= 0) && (r < (int)grid.size());        bool bCol = (c >= 0) && (c < (int)grid[0].size());        return bRow && bCol;}//void dfs(int[][] grid, int r, int c) {void dfs(vector>& grid, int r,int c){        //判断base case        //如果坐标(r,c)超出了网格范围，则直接返回        if (!inArea(grid,r,c)) {                return;        }        //如果不是岛屿，则直接返回        if (grid[r][c] != '1') {                return;        }        //将原来的"1"改成"0"        grid[r][c] = '2';        //访问上、下、左、右四个相邻结点        dfs(grid, r - 1, c);        dfs(grid, r + 1, c);        dfs(grid, r , c-1);        dfs(grid, r , c+1);}//求岛屿的个数//时间复杂度：O(MN)O(MN)，其中 MM 和 NN 分别为行数和列数。//空间复杂度：O(MN)O(MN)，在最坏情况下，整个网格均为陆地，深度优先搜索的深度达到MN。//int numIslands(vector>& grid){        int r = grid.size();        if (!r)                return 0;        int c = grid[0].size();        int num = 0;        for (int i = 0; i < r; i++) {                for (int j = 0; j < c; j++) {                        if (grid[i][j] == '1') {                                ++num;                                dfs(grid, i, j);                        }                }        }        return num;}int main(){        //岛屿        // 1  1  1        // 0  1  0        // 1  0  0        // 1  0  1        vector row1;        row1.push_back('1');        row1.push_back('1');        row1.push_back('1');        vector row2;        row2.push_back('0');        row2.push_back('1');        row2.push_back('0');        vector row3;        row3.push_back('1');        row3.push_back('0');        row3.push_back('0');        vector row4;        row4.push_back('1');        row4.push_back('0');        row4.push_back('1');        vector> grid;        grid.push_back(row1);        grid.push_back(row2);        grid.push_back(row3);        grid.push_back(row4);        int numLands = numIslands(grid);        cout << "numLands= " << numLands << endl;        system("pause");        return 0;}

效果如下：

2、go语言实现

//island.go

package mainimport "fmt"func numIslands(grid [][]byte) int {        nums := 0        for i:=0; i=row || j<0 || j>= col {                return        }        if (*grid)[i][j] == '1' {                (*grid)[i][j] = '2'                DFS(grid,i-1,j)                DFS(grid,i+1,j)                DFS(grid,i,j-1)                DFS(grid,i,j+1)        }}func main() {        var grid = make([][]byte, 4)        grid[0] = []byte{'1','1','1'}        grid[1] = []byte{'0','1','0'}        grid[2] = []byte{'1','0','0'}        grid[3] = []byte{'1','0','1'}        res := numIslands(grid)        fmt.Println("numlands=",res)}

效果如下：

"怎么用C++或Go求矩阵里的岛屿的数量"的内容就介绍到这里了，感谢大家的阅读。如果想了解更多行业相关的知识可以关注网站，小编将为大家输出更多高质量的实用文章！