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; }
效果如下:
图(1) 孤岛的个数
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) }
效果如下:
图(2) go语言实现,求岛屿的个数
参考文献
来源:力扣(LeetCode)
总结
本篇文章就到这里了,希望能够给你带来帮助,也希望您能够多多关注我们的更多内容!
赞 (0)