একটি 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;
}
};
