C++或Go求矩陣里的島嶼的數(shù)量詳解
更新時間：2021年09月09日 14:30:35 作者：sanqima
這篇文章主要介紹了C++和go實現(xiàn)LeetCode(200.島嶼的數(shù)量),本篇文章通過簡要的案例,講解了該項技術的了解與使用,以下就是詳細內容,需要的朋友可以參考下
給你一個由 ‘1'（陸地）和 ‘0'（水）組成的的二維網格，請你計算網格中島嶼的數(shù)量。
島嶼總是被水包圍，并且每座島嶼只能由水平方向和/或豎直方向上相鄰的陸地連接形成。此外，你可以假設該網格的四條邊均被水包圍。
示例 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++實現(xiàn)
//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);
}
//求島嶼的個數(shù)
//時間復雜度：O(MN)O(MN)，其中 MM 和 NN 分別為行數(shù)和列數(shù)。
//空間復雜度：O(MN)O(MN)，在最壞情況下，整個網格均為陸地，深度優(yōu)先搜索的深度達到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語言實現(xiàn)
//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)
}
效果如下：
參考文獻
來源：力扣（LeetCode）
總結
本篇文章就到這里了，希望能夠給你帶來幫助，也希望您能夠多多關注腳本之家的更多內容！
相關文章
占位符是一種用于格式化輸出的特殊字符，通常用于 printf() 等輸出函數(shù)中，本文主要介紹了C語言常用占位符的使用小結，非常具有實用價值，需要的朋友可以參考下2023-05-05
這篇文章主要介紹了VC枚舉串口端口應用,羅列了常見的一些串口端口的應用實例,需要的朋友可以參考下2014-10-10
今天小編就為大家分享一篇關于C語言數(shù)組a和&a的區(qū)別講解，小編覺得內容挺不錯的，現(xiàn)在分享給大家，具有很好的參考價值，需要的朋友一起跟隨小編來看看吧2019-02-02
這篇文章主要為大家詳細介紹了C語言實現(xiàn)簡單的貪吃蛇游戲，文中示例代碼介紹的非常詳細，具有一定的參考價值，感興趣的小伙伴們可以參考一下2021-07-07
這篇文章主要介紹了C++11 線程休眠函數(shù)的相關資料，幫助大家更好的理解和學習C++11,感興趣的朋友可以了解下2020-10-10
這篇文章主要為大家詳細介紹了opencv+arduino實現(xiàn)物體點追蹤效果，具有一定的參考價值，感興趣的小伙伴們可以參考一下2018-01-01
OpenCV+Qt實現(xiàn)圖像處理操作工具的示例代碼
這篇文章主要介紹了利用OpenCV+Qt實現(xiàn)圖像處理操作工具，可以實現(xiàn)雪花屏、高斯模糊、中值濾波、毛玻璃等操作，感興趣的可以了解一下2022-08-08
本篇文章是對c語言中調試工具的用法進行了匯總，需要的朋友參考下2013-05-05
C++是大家都非常熟悉的,也是大家平時辦公中經常會用到的,下面這篇文章主要給大家介紹了關于C++連接mysql數(shù)據(jù)庫的相關資料,文中通過代碼介紹的非常詳細,需要的朋友可以參考下2023-12-12
這篇文章主要介紹了C++中運算符 &和&&、|和|| 的詳解及區(qū)別的相關資料,這里舉例說明該如何區(qū)別他們的不同，需要的朋友可以參考下2016-11-11