目录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.lengthn == grid[i].length1 <= m, n <= 300grid[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 1vector<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;}
效果如下：
图(1) 孤岛的个数
2、go语言实现
//island.go
package mainimport "fmt"func numIslands(grid [][]byte) int {nums := 0for 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)}
效果如下：
图(2) go语言实现，求岛屿的个数
参考文献
来源：力扣（LeetCode）
总结
本篇文章就到这里了，希望能够给你带来帮助，也希望您能够多多关注自由互联的更多内容！
看着你手中的戒指，你说，你可以把它取下来吗？
