Trong bài toán này, chúng ta được đưa ra một ma trận nhị phân 2D. Nhiệm vụ của chúng tôi là tìm số đảo bằng cách sử dụng DFS .
Đảo là mặt bằng của 1 hoặc nhiều số 1 được kết nối trong ma trận.
Hãy lấy một ví dụ để hiểu vấn đề,
Đầu vào
bin[][] = {{ 1 0 0 0}
{0 1 0 1}
{0 0 0 0}
{0 0 1 0}} Đầu ra
3
Giải thích
Islands are : bin00 - bin11 bin13 bin32
Phương pháp tiếp cận giải pháp
Để tìm đảo từ ma trận nhị phân bằng cách sử dụng cấu trúc dữ liệu tập hợp rời rạc. Để tìm số đảo, chúng ta sẽ duyệt qua ma trận và thực hiện liên kết của tất cả các đỉnh liền kề bằng cách kiểm tra tất cả 8 lân cận, nếu chúng là 1 thì lấy liên hợp của chỉ mục hiện tại với lân cận của nó. Sau đó, thực hiện chuyển ngang thứ hai của ma trận và nếu tại bất kỳ chỉ mục nào giá trị là 1, hãy tìm giá trị đã gửi của nó. Nếu tần suất là 0, hãy tăng lên 1.
Ví dụ
Chương trình minh họa hoạt động của giải pháp của chúng tôi,
#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);
} Đầu ra
The number of islands in binary matrix is : 4