বাইনারি ম্যাট্রিক্সে স্বতন্ত্র দ্বীপের সংখ্যা C++-এ

সমস্যা বিবরণ

একটি বাইনারি ২D গ্রিড দেওয়া আছে। ১ = ল্যান্ড, ০ = পানি। ৪-দিকই কানেক্টেড ল্যান্ড গ্রুপকে দ্বীপ বলা হয়। দুটি দ্বীপ একই মনে হবে যদি একটিকে ট্রান্সলেট (translate) করে অন্যটির সাথে মিলানো যায় (রোটেশন বা রিফ্লেকশন নয়)। স্বতন্ত্র দ্বীপের সংখ্যা বের করতে হবে।

উদাহরণ

ইনপুট গ্রিড:

1 1 0 1 1
1 0 0 0 0
0 0 0 0 1
1 1 0 1 1

অ্যালগরিদম: DFS + শেপ সিগনেচার

1. প্রতিটি অনভিজিটেড ১-সেল থেকে DFS চালান।
2. DFS এর время পাথ রেকর্ড করুন: যেটি ডিরেকশন চেন্জ হয় (r, l, u, d) এবং ব্যাকট্র্যাকিং (b) দিয়ে এনকোড করুন।
3. এই পাথ স্ট্রিংই দ্বীপের শেপ সিগনেচার।
4. সেটে সিগনেচার স্টোর করুন। ইউনিক সিগনেচার সংখ্যাই উত্তর।

C++ বাস্তবায়ন

#include <bits/stdc++.h>
using namespace std;

class Solution {
public:
    void dfs(int x, int y, vector<vector<int>>& grid, string& path, char dir) {
        if (x < 0 || y < 0 || x >= grid.size() || y >= grid[0].size() || !grid[x][y]) return;
        grid[x][y] = 0; // ভিজিটেড মার্ক
        path += dir;
        dfs(x+1, y, grid, path, 'r');
        dfs(x-1, y, grid, path, 'l');
        dfs(x, y+1, grid, path, 'd');
        dfs(x, y-1, grid, path, 'u');
        path += 'b'; // ব্যাকট্র্যাক
    }

    int numDistinctIslands(vector<vector<int>>& grid) {
        set<string> shapes;
        for (int i = 0; i < grid.size(); i++) {
            for (int j = 0; j < grid[0].size(); j++) {
                if (grid[i][j]) {
                    string path = "";
                    dfs(i, j, grid, path, 's'); // 's' = старт
                    shapes.insert(path);
                }
            }
        }
        return shapes.size();
    }
};

int main() {
    Solution ob;
    vector<vector<int>> v = {{1,1,0,1,1},{1,0,0,0,0},{0,0,0,0,1},{1,1,0,1,1}};
    cout << ob.numDistinctIslands(v); // আউটপুট: 3
    return 0;
}

ইনপুট ও আউটপুট

জটিলতা বিশ্লেষণ

• সময় জটিলতা: O(R × C) — R = সারি, C = কলাম। প্রতিটি সেল একবার ভিজিট।
• স্থান জটিলতা: O(R × C) — রিকার্সন স্ট্যাক ও সেট (সর্বোচ্চ)।