মডিউল ৯_৩ঃ Max Area of Island [Leetcode]

আপনাকে একটি m x n বাইনারি ম্যাট্রিক্স গ্রিড দেওয়া হয়েছে। দ্বীপকে 1 দ্বারা রিপ্রেজেন্ট করা হয়েছে,

যা 4-দিক দিয়ে সংযুক্ত (অনুভূমিক বা উল্লম্ব) । আপনি ধরে নিতে পারেন গ্রিডের চারটি প্রান্তই জল দ্বারা বেষ্টিত।

একটি দ্বীপের ক্ষেত্রফল হল সেই দ্বীপে মোট cell সংখ্যার।

এখন আপনার থেকে বের করতে হবে সবোচ্ছ ক্ষেত্রফল কত কোন একটা দ্বীপের সেইটি রিটান করতে হবে। যদি গ্রিডে কোন দ্বীপের না থাকে তাহলে 0 রিটান করবেন।

উপরের চিত্রে ৬টি দ্বীপ রয়েছে। এই ৬টি দ্বীপের মধ্যে সবোচ্ছ ক্ষেত্রফল আছে ৬।

সমাধান

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

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

vis array তে false assign করেছি। mx = 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)
        {
            ans = 0;
            dfs(i, j, grid);
            mx = max(mx, ans);
        }
    }
}

এখন nested লুপ চালিয়েছি, সেই grid আনভিজিটেড কিনা এবং grid ==1 কিনা চেক করে, ans variable কে refresh করেছি। dfs কে কল করেছি। dfs function complete হওয়ার পর ans এবং mx থেকে যেইটি বড় সেইটিকে mx এ assign করেছি।

void dfs(int si, int sj, vector<vector<int>> &grid)
{
    vis[si][sj] = true;
    ans++;
    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 কে ভিজিটেড করেছি, এরপর সাথেই ans++ করেছি। এরপর grid এর উপরে , নিচে , ডানে , বামে যাওয়ার জন্য লুপ চালিয়েছি। যদি ci, cj ভ্যালিড এবং আনভিজিটেড এবং grid[ci][cj]==1 হয় তাহলে ci,cj কে দিয়ে dfs function কে recursive কল করবো।

সম্পূর্ণ কোড

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

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