এই সমস্যাতে, আমাদের একটি ২D বাইনারি ম্যাট্রিক্স দেওয়া আছে। আমাদের কাজ হল DFS ব্যবহার করে দ্বীপের সংখ্যা বের করা।
দ্বীপ (Island) হল ম্যাট্রিক্সে ১ বা অধিক সংযুক্ত ১-এর গোষ্ঠী।
উদাহরণ দেখি:
ইনপুট
bin[][] = {{ 1 0 0 0} {0 1 0 1} {0 0 0 0} {0 0 1 0}}
আউটপুট
3
ব্যাখ্যা
দ্বীপগুলো: bin00 - bin11 bin13 bin32
সমাধানের পদ্ধতি
বাইনারি ম্যাট্রিক্স থেকে দ্বীপের সংখ্যা বের করতে ডিজয়েন্ট সেট ডেটা স্ট্রাকচার ব্যবহার করা হয়। ম্যাট্রিক্স ট্রাভার্স করে সব এডজেসেন্ট ভার্টেক্সের ইউনিয়ন করা হয় ৮টি প্রতিবেশী চেক করে। যদি ১ থাকে, তবে করেন্ট ইনডেক্সের সাথে তার প্রতিবেশীর ইউনিয়ন করা হয়। তারপর দ্বিতীয় ট্রাভার্সালে, যদি কোনো ইনডেক্সে ১ থাকে, তবে তার সেন্ট (parent) বের করা হয়। যদি ফ্রিকোয়েন্সি ০ থাকে, তবে ১ করে দ্বীপের সংখ্যা বাড়ানো হয়।
উদাহরণ
#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
