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

একটি m x n 2D বাইনারি গ্রিড দেওয়া হয়েছে যা '1' (ভূমি) এবং '0' (জল) রিপ্রেজেন্ট করা হয়েছে, আপনার থেকে বের করতে হবে গ্রিডে কয়টি দ্বীপ রয়েছে।

ভূমিগুলো অনুভূমিকভাবে বা উল্লম্বভাবে ভাবে একত্রিত হয়ে আছে। একটি দ্বীপ জল দ্বারা বেষ্টিত থাকে।

উপরের চিত্রের গ্রিডটিতে ৩ টি দ্বীপ পাওয়া গিয়েছে। গ্রিডটিতে কয়টি দ্বীপ আছে সেইটি আপনার থেকে রিটার্ন করতে হবে।

সমাধান

এই প্রব্লেমটিতে grid[i][j] ==1 পেলে এবং সেইটি আনভিজিটেড হলে সেইটিকে dfs দিয়ে traversal করবো, এইভাবে যতবার dfs কল করেছি ততবার এক একটি দ্বীপকে traverse করেছি এবং দ্বীপকে count করেছি।

n = grid.size();
m = grid[0].size();
memset(vis, false, sizeof(vis));
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] == '1')
        {
            dfs(i, j, grid);
            ans++;
        }
    }
}

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

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

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

সম্পূর্ণ কোড

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

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