মডিউল ৯_৬ঃ Number of Closed Islands [Leetcode]

একটি 2D গ্রিড 0 (ভূমি) এবং 1 (জল) নিয়ে গঠিত। একটি বদ্ধ দ্বীপ হল যা ভূমি (0) দিয়ে গঠিত এবং দ্বীপের মধ্যে জল(1) থাকতে পারে , যেইটি সম্পূর্ণভাবে (সমস্ত বাম, উপরে, ডান, নীচে) 1s দ্বারা বেষ্টিত।

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

উপরের চিত্রে ২ টি বদ্ধ দ্বীপ পাওয়া গেছে, বদ্ধ দ্বীপকে হলুদ কালার দিয়ে চিন্থিত করা হয়েছে।

সমাধান

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

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

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

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

flag variable কে refresh করেছি,

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

void dfs(int si, int sj, vector<vector<int>> &grid)
{
    vis[si][sj] = true;
    if (si == 0 || si == n - 1 || sj == 0 || sj == m - 1)
        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] && grid[ci][cj] == 0)
        {
            dfs(ci, cj, grid);
        }
    }
}

dfs function এ প্রথমে si এবং sj কে ভিজিটেড করেছি, এরপর

si , sj outer সাইডে চলে গেলে flag = false করেছি।

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

সম্পূর্ণ কোড

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

class Solution
{
public:
    int n, m;
    bool vis[105][105];
    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>> &grid)
    {
        vis[si][sj] = true;
        if (si == 0 || si == n - 1 || sj == 0 || sj == m - 1)
            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] && grid[ci][cj] == 0)
            {
                dfs(ci, cj, grid);
            }
        }
    }
    int closedIsland(vector<vector<int>> &grid)
    {
        memset(vis, false, sizeof(vis));
        n = grid.size();
        m = grid[0].size();
        int ans = 0;
        for (int i = 0; i < n; i++)
        {
            for (int j = 0; j < m; j++)
            {
                if (!vis[i][j] && grid[i][j] == 0)
                {
                    flag = true;
                    dfs(i, j, grid);
                    if (flag == true)
                    {
                        ans++;
                    }
                }
            }
        }
        return ans;
    }
};