মডিউল ৯_১ঃ Island Perimeter [Leetcode]

আপনাকে একটি ম্যাপ এ row x col grid দেওয়া হয়েছে যেখানে grid[i][j] = 1 ভূমিকে রিপ্রেজেন্ট করে এবং গ্রিড[i][j] = 0 জলকে রিপ্রেজেন্ট করে।

Grid গুলি অনুভূমিকভাবে/উল্লম্বভাবে সংযুক্ত থাকে (তির্যকভাবে নয়)। Grid সম্পূর্ণরূপে জল দ্বারা বেষ্টিত, এবং ঠিক একটি দ্বীপ আছে (অর্থাৎ, এক বা একাধিক সংযুক্ত ভূমি)।

দ্বীপটিতে 'হ্রদ' নেই, অর্থাৎ দ্বীপের মধ্যে জল থাকবে না। একটি cell হল একটি বর্গক্ষেত্র যার পাশের দৈর্ঘ্য 1। গ্রিডটি আয়তক্ষেত্রাকার, প্রস্থ এবং উচ্চতা 100 এর বেশি নয়। দ্বীপের perimeter বের করতে হবে।

উপরের চিত্রে perimeter হবে 16। হলুদ কালার করা গুলো এক একটি perimeter।

সমাধান

এই প্রব্লেমটি সমাধান করতে আমরা দেখবো কোন একটা grid ( যেইটির মান 1 ) এর উপরে নিচে ডানে বামে কোথাও ভ্যালিড grid ( যেইটির মান 1 ) থাকলে তখন আমরা perimeter count করবো না, অন্যথায় perimeter count করবো।

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

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);
        }
    }
}

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

void dfs(int si, int sj, vector<vector<int>> &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))
        {
            if (grid[ci][cj] == 0)
                ans++;
        }
        else
        {
            ans++;
        }
        if (valid(ci, cj) && !vis[ci][cj] && grid[ci][cj] == 1)
        {
            dfs(ci, cj, grid);
        }
    }
}

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

সম্পূর্ণ কোডটি

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

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