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

目录

• 1、C++实现
• 2、go语言实现
• 参考文献
• 总结

#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  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= " <

package main
import "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)
}