মডিউল ৯_৫ঃ Count Sub Islands [Leetcode]

আপনাকে দুটি m x n বাইনারি ম্যাট্রিস গ্রিড 1 এবং গ্রিড 2 দেওয়া হয়েছে যেখানে শুধুমাত্র 0 (জল রিপ্রেজেন্ট করে) এবং 1 (ভূমি রিপ্রেজেন্ট করে) রয়েছে। দ্বীপকে 1 দ্বারা রিপ্রেজেন্ট করা হয়েছে, যা 4-দিক দিয়ে সংযুক্ত (অনুভূমিক বা উল্লম্ব)

গ্রিড 2-এর একটি দ্বীপকে একটি উপ-দ্বীপ হিসাবে বিবেচনা করা হবে যদি গ্রিড 1-এ ওই দ্বীপটি থাকে

আপনার থেকে উপ-দ্বীপ সংখ্যা বের করতে হবে।

উপরের চিত্রে এইরকম ৩টি উপ-দ্বীপ পাওয়া গিয়েছে।

সমাধান

এই প্রব্লেমটি আমরা grid2 দিয়ে dfs চালিয়ে traverse করেছি , আর এই traverse চলাকালীন চেক করেছি সেই si , sj তে grid1 এর মধ্যেও ভূমি আছে কিনা। যদি grid2 থেকে traverse করার সময় সবগুলোতে grid1 ভূমি পাওয়ার যায় তাহলে sub islands count করবো।

memset(vis, false, sizeof(vis));
n = grid2.size();
m = grid2[0].size();
int ans = 0;

vis array তে false assign করেছি। ans = 0 নিয়েছি, n এ grid2 এর number of row এবং m এ grid2 এর number of col রেখেছি।

for (int i = 0; i < n; i++)
{
    for (int j = 0; j < m; j++)
    {
        if (!vis[i][j] && grid2[i][j] == 1)
        {
            flag = true;
            dfs(i, j, grid1, grid2);
            if (flag == true)
                ans++;
        }
    }
}

এখন nested লুপ চালিয়েছি, সেই grid2 আনভিজিটেড কিনা এবং grid2 ==1 কিনা চেক করে

flag variable কে refresh করেছি,

dfs কে কল করেছি এবং ans++ করেছি। dfs function complete হওয়ার পর flag==true হলে sub islands count করেছি।

void dfs(int si, int sj, vector<vector<int>> &grid1, vector<vector<int>> &grid2)
{
    vis[si][sj] = true;
    if (grid1[si][sj] == 0)
        flag = false;
    for (int i = 0; i < 4; i++)
    {
        int ci = si + d[i].first;
        int cj = sj + d[i].second;
        if (valid(ci, cj) && !vis[ci][cj] && grid2[ci][cj] == 1)
        {
            dfs(ci, cj, grid1, grid2);
        }
    }
}

dfs function এ প্রথমে si এবং sj কে ভিজিটেড করেছি, এরপর grid1 এর si, sj 0 হলে flag = false করেছি।

এরপর grid2 এর উপরে , নিচে , ডানে , বামে যাওয়ার জন্য লুপ চালিয়েছি। যদি ci, cj ভ্যালিড এবং আনভিজিটেড এবং grid2[ci][cj]==1 হয় তাহলে ci,cj কে দিয়ে dfs function কে recursive কল করবো।

সম্পূর্ণ কোড

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

class Solution
{
public:
    int n, m;
    bool vis[505][505];
    vector<pair<int, int>> d = {{0, 1}, {0, -1}, {-1, 0}, {1, 0}};
    bool valid(int ci, int cj)
    {
        if (ci >= 0 && ci < n && cj >= 0 && cj < m)
            return true;
        else
            return false;
    }
    bool flag;
    void dfs(int si, int sj, vector<vector<int>> &grid1, vector<vector<int>> &grid2)
    {
        vis[si][sj] = true;
        if (grid1[si][sj] == 0)
            flag = false;
        for (int i = 0; i < 4; i++)
        {
            int ci = si + d[i].first;
            int cj = sj + d[i].second;
            if (valid(ci, cj) && !vis[ci][cj] && grid2[ci][cj] == 1)
            {
                dfs(ci, cj, grid1, grid2);
            }
        }
    }
    int countSubIslands(vector<vector<int>> &grid1, vector<vector<int>> &grid2)
    {
        memset(vis, false, sizeof(vis));
        n = grid2.size();
        m = grid2[0].size();
        int ans = 0;
        for (int i = 0; i < n; i++)
        {
            for (int j = 0; j < m; j++)
            {
                if (!vis[i][j] && grid2[i][j] == 1)
                {
                    flag = true;
                    dfs(i, j, grid1, grid2);
                    if (flag == true)
                        ans++;
                }
            }
        }
        return ans;
    }
};