怎么用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求矩陣里的島嶼的數量”的內容就介紹到這里了，感謝大家的閱讀。如果想了解更多行業相關的知識可以關注億速云網站，小編將為大家輸出更多高質量的實用文章！