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

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

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

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

<figure><img src="https://1548341763-files.gitbook.io/~/files/v0/b/gitbook-x-prod.appspot.com/o/spaces%2FjliRFwU9cGQFGljHYgOZ%2Fuploads%2F5wRIvVysXHBmyC7zLHkh%2Fimage.png?alt=media&#x26;token=7229dc48-ffaa-446e-8061-59ff6b572039" alt="" width="563"><figcaption></figcaption></figure>

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

## সমাধান&#x20;

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

```cpp
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 রেখেছি।&#x20;

```cpp
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 করেছি,&#x20;

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

```cpp
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 করেছি।&#x20;

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

## সম্পূর্ণ কোড

```cpp
#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;
    }
};
```