যোগাযোগ টাওয়ার গ্রুপ গণনা C++-এ

একটি ২D বাইনারি ম্যাট্রিক্সে ১টি যোগাযোগ টাওয়ার এবং ০ খালি সেল বোঝায়। একই সারি বা কলামে থাকা টাওয়ারগুলো একে অপরের সাথে যোগাযোগ করতে পারে। ট্রানজিটিভ প্রোপার্টি অনুযায়ী, যদি A, B-র সাথে এবং B, C-র সাথে কথা বলে, তবে A, C-র সাথে কথা বলতে পারবে। মোট কতগুলো টাওয়ার গ্রুপ আছে তা বের করতে হবে।

উদাহরণ

ম্যাট্রিক্স:

1 1 0
0 0 1
1 0 1

আউটপুট: 1 (সব টাওয়ার একটি গ্রুপে)

অ্যালগরিদম (DFS)

প্রতিটি সেলের জন্য যদি ১ পাওয়া যায়, তবে গ্রুপ কাউন্ট বাড়ান এবং DFS চালু করুন।
DFS-এ বর্তমান সেলকে ভিজিটেড মার্ক করুন (২ দিয়ে)।
একই সারির সব সেল এবং একই কলামের সব সেল চেক করুন।
যেখানে ১ পাওয়া যায়, সেখানে রিকারসিভলি DFS কল করুন।

C++ কোড উদাহরণ

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

class Solution {
public:
    void dfs(vector>& matrix, int i, int j, int& n, int& m) {
        matrix[i][j] = 2; // visited
        
        // Same column (all rows)
        for (int k = 1; k < n; k++) {
            int p = (i + k) % n, q = j;
            if (matrix[p][q] == 1)
                dfs(matrix, p, q, n, m);
        }
        
        // Same row (all columns)
        for (int k = 1; k < m; k++) {
            int p = i, q = (j + k) % m;
            if (matrix[p][q] == 1)
                dfs(matrix, p, q, n, m);
        }
    }
    
    int solve(vector>& matrix) {
        int n = matrix.size(), m = matrix[0].size();
        int ans = 0;
        
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                if (matrix[i][j] == 1) {
                    ans++;
                    dfs(matrix, i, j, n, m);
                }
            }
        }
        return ans;
    }
};

int main() {
    Solution ob;
    vector> v = {
        {1, 1, 0},
        {0, 0, 1},
        {1, 0, 1}
    };
    cout << ob.solve(v);
    return 0;
}

ইনপুট

{{1,1,0}, {0,0,1}, {1,0,1}}