資料結構
網路
RDBMS
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會研究
時尚研究
法律研究使用 C++ 的 disjoint set 查詢島嶼數量
在這個問題中，我們被給了一個 2D 二進位制矩陣。我們的任務是使用 DFS 查詢島嶼數量。
島嶼是矩陣中一個或多個相連的 1 的塊。
讓我們舉一個例子來理解這個問題，
輸入
bin[][] = {{ 1 0 0 0}
{0 1 0 1}
{0 0 0 0}
{0 0 1 0}}輸出
3
說明
Islands are : bin00 - bin11 bin13 bin32
解決方法
使用不相交集資料結構從二進位制矩陣中查詢島嶼。要查詢島嶼數量，我們將遍歷矩陣並透過檢查所有 8 個鄰居，將所有相鄰頂點進行聯合，如果它們是 1，則將當前索引與其鄰居聯合。然後對矩陣進行第二次遍歷，如果在任何索引處值為 1，則查詢其 sent。如果頻率為 0，則增加到 1。
例子
說明我們解決方案工作原理的程式，
#include <bits/stdc++.h>
using namespace std;
class DisjointUnionSets{
vector<int> rank, parent;
int n;
public:
DisjointUnionSets(int n){
rank.resize(n);
parent.resize(n);
this->n = n;
makeSet();
}
void makeSet(){
for (int i = 0; i < n; i++)
parent[i] = i;
}
int find(int x){
if (parent[x] != x){
return find(parent[x]);
}
return x;
}
void Union(int x, int y){
int xRoot = find(x);
int yRoot = find(y);
if (xRoot == yRoot)
return;
if (rank[xRoot] < rank[yRoot])
parent[xRoot] = yRoot;
else if (rank[yRoot] < rank[xRoot])
parent[yRoot] = xRoot;
else {
parent[yRoot] = xRoot;
rank[xRoot] = rank[xRoot] + 1;
}
}
};
int findIslandCount(vector<vector<int>> mat){
int n = mat.size();
int m = mat[0].size();
DisjointUnionSets *dus = new DisjointUnionSets(n * m);
for (int j = 0; j < n; j++){
for (int k = 0; k < m; k++){
if (mat[j][k] == 0)
continue;
if (j + 1 < n && mat[j + 1][k] == 1)
dus->Union(j * (m) + k, (j + 1) * (m) + k);
if (j - 1 >= 0 && mat[j - 1][k] == 1)
dus->Union(j * (m) + k, (j - 1) * (m) + k);
if (k + 1 < m && mat[j][k + 1] == 1)
dus->Union(j * (m) + k, (j) * (m) + k + 1);
if (k - 1 >= 0 && mat[j][k - 1] == 1)
dus->Union(j * (m) + k, (j) * (m) + k - 1);
if (j + 1 < n && k + 1 < m && mat[j + 1][k + 1] == 1)
dus->Union(j * (m) + k, (j + 1) * (m) + k + 1);
if (j + 1 < n && k - 1 >= 0 && mat[j + 1][k - 1] == 1)
dus->Union(j * m + k, (j + 1) * (m) + k - 1);
if (j - 1 >= 0 && k + 1 < m && mat[j - 1][k + 1] == 1)
dus->Union(j * m + k, (j - 1) * m + k + 1);
if (j - 1 >= 0 && k - 1 >= 0 && mat[j - 1][k - 1] == 1)
dus->Union(j * m + k, (j - 1) * m + k - 1);
}
}
int *c = new int[n * m];
int islands = 0;
for (int j = 0; j < n; j++){
for (int k = 0; k < m; k++){
if (mat[j][k] == 1){
int x = dus->find(j * m + k);
if (c[x] == 0){
islands++;
c[x]++;
}
else
c[x]++;
}
}
}
return islands;
}
int main(void){
vector<vector<int>> mat = {
{1, 1, 0, 1, 0},
{0, 1, 0, 1, 1},
{1, 0, 0, 1, 1},
{0, 0, 0, 0, 0},
{1, 1, 1, 0, 1}
};
cout<<"The number of islands in binary matrix is : "<<findIslandCount(mat);
}輸出
The number of islands in binary matrix is : 4
更新於： 2022-02-11
444 次瀏覽
廣告