怎么用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 <iostream> #include <algorithm> #include <string> #include <vector> using namespace std; //判断坐标(r,c)是否存在网络中 bool inArea(vector<vector<char>>& 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<vector<char>>& 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<vector<char>>& 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<char> row1;	row1.push_back('1');	row1.push_back('1');	row1.push_back('1');	vector<char> row2;	row2.push_back('0');	row2.push_back('1');	row2.push_back('0');	vector<char> row3;	row3.push_back('1');	row3.push_back('0');	row3.push_back('0');	vector<char> row4;	row4.push_back('1');	row4.push_back('0');	row4.push_back('1');	vector<vector<char>> 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 main import "fmt" func numIslands(grid [][]byte) int {	nums := 0	for i:=0; i<len(grid); i++ {	for j:=0; j<len(grid[0]); j++ {	if grid[i][j] == '1' {	DFS(&grid,i,j)	nums++	}	}	}	return nums } func DFS(grid *[][]byte, i int, j int) {	var (	row = len(*grid)	col = len((*grid)[0])	)	if 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求矩阵里的岛屿的数量”的内容就介绍到这里了，感谢大家的阅读。如果想了解更多行业相关的知识可以关注亿速云网站，小编将为大家输出更多高质量的实用文章！