ধরা যাক grid নামে একটি নন-এমপ্টি 2D বাইনারি অ্যারে আছে, এখানে একটি দ্বীপ হল ১'র (ল্যান্ড রিপ্রেজেন্ট করে) একটি গ্রুপ যা ৪-দিকernos সংযুক্ত। আমরা চারদিকের এজগুলো পানি দিয়ে ঘেরা আছে ধরে নিতে পারি।
আমাদের সতেজ দ্বীপের সংখ্যা গণনা করতে হবে। একটি দ্বীপ অন্যটির সাথে একই মনে হবে যদি তাদের আকার একই হয়, বা ৯০, ১৮০, বা ২৭০ ডিগ্রি ঘুরালে আকার একই হয় বা বাম/ডান বা উপর/নিচ রিফ্লেকশনের পর আকার একই হয়।
তাই, যদি ইনপুট যেন,
| 1 | 1 | 0 | 0 | 0 |
| 1 | 0 | 0 | 0 | 0 |
| 0 | 0 | 0 | 0 | 1 |
| 0 | 0 | 0 | 1 | 1 |
হয়, তবে আউটপুট হবে ১
এটি সমাধান করতে, আমরা নিচের ধাপগুলো অনুসরণ করব -
একটি ম্যাপ m ডিফাইন করুন
একটি dfs() ফাংশন ডিফাইন করুন, এটি i, j, grid, idx নেবে,
যদি i এবং j grid-এর রেঞ্জের মধ্যে থাকে এবং grid[i,j] ০ হয় তবে -
রিটার্ন
grid[i, j] := 0
{ i, j } m[idx]-এর শেষে ইনসার্ট করুন
dfs(i + 1, j, grid, idx)
dfs(i - 1, j, grid, idx)
dfs(i, j - 1, grid, idx)
dfs(i, j + 1, grid, idx)
একটি norm() ফাংশন ডিফাইন করুন, এটি একটি অ্যারে v নেবে
পেয়ারের ৮টি রো সহ একটি 2D অ্যারে s ডিফাইন করুন
i := 0 থেকে শুরু করুন, যখন i < v-এর আকার, (i ১ করে বাড়ান), করুন -
x := v[i].first
y := v[i].second
{ x, y } s[0]-এর শেষে ইনসার্ট করুন
{ x, -y } s[1]-এর শেষে ইনসার্ট করুন
{ -x, y } s[2]-এর শেষে ইনসার্ট করুন
{ -x, -y } s[3]-এর শেষে ইনসার্ট করুন
{ y, x } s[4]-এর শেষে ইনসার্ট করুন
{ y, -x } s[5]-এর শেষে ইনসার্ট করুন
{ -y, x } s[6]-এর শেষে ইনসার্ট করুন
{ -y, -x } s[7]-এর শেষে ইনসার্ট করুন
i := 0 থেকে শুরু করুন, যখন i < s-এর আকার, (i ১ করে বাড়ান), করুন -
অ্যারে s[i] সর্ট করুন
i := 0 থেকে শুরু করুন, যখন i < s-এর আকার, (i ১ করে বাড়ান), করুন -
j := 1 থেকে শুরু করুন, যখন j < v-এর আকার, (j ১ করে বাড়ান), করুন -
s[i, j].first := s[i, j].first - s[i, 0].first
s[i, j].second := s[i, j].second - s[i, 0].second
s[i, 0].first := 0
s[i, 0].second := 0
অ্যারে s সর্ট করুন
s[0] রিটার্ন করুন
মূল মেথড থেকে নিচের কাজগুলো করুন -
একটি সেট pts ডিফাইন করুন
cnt := 1
i := 0 থেকে শুরু করুন, যখন i < grid-এর আকার, (i ১ করে বাড়ান), করুন -
j := 0 থেকে শুরু করুন, যখন j < grid[0]-এর আকার, (j ১ করে বাড়ান), করুন &miuns;-
যদি grid[i, j], ১-এর সমান হয়, তবে -
(cnt ১ করে বাড়ান)
dfs(i, j, grid, cnt)
norm(m[cnt]) pts-এ ইনসার্ট করুন
pts-এর আকার রিটার্ন করুন
বेहतर বোঝার জন্য নিচের বাস্তবায়নটি দেখুন -
উদাহরণ
#include <bits/stdc++.h> using namespace std; class Solution { public: map < int, vector < pair <int, int> > > m; void dfs(int i, int j, vector < vector <int> >& grid, int idx){ if (i >= grid.size() || j >= grid[0].size() || i < 0 || !grid[i][j]) return; grid[i][j] = 0; m[idx].push_back({ i, j }); dfs(i + 1, j, grid, idx); dfs(i - 1, j, grid, idx); dfs(i, j - 1, grid, idx); dfs(i, j + 1, grid, idx); } vector < pair <int, int> > norm(vector < pair < int, int > > v){ vector<vector<pair<int, int> > > s(8); for (int i = 0; i < v.size(); i++) { int x = v[i].first; int y = v[i].second; s[0].push_back({ x, y }); s[1].push_back({ x, -y }); s[2].push_back({ -x, y }); s[3].push_back({ -x, -y }); s[4].push_back({ y, x }); s[5].push_back({ y, -x }); s[6].push_back({ -y, x }); s[7].push_back({ -y, -x }); } for (int i = 0; i < s.size(); i++) { sort(s[i].begin(), s[i].end()); } for (int i = 0; i < s.size(); i++) { for (int j = 1; j < v.size(); j++) { s[i][j].first = s[i][j].first - s[i][0].first; s[i][j].second = s[i][j].second - s[i][0].second; } s[i][0].first = 0; s[i][0].second = 0; } sort(s.begin(), s.end()); return s[0]; } int numDistinctIslands2(vector<vector<int>>& grid) { set<vector<pair<int, int> > > pts; int cnt = 1; for (int i = 0; i < grid.size(); i++) { for (int j = 0; j < grid[0].size(); j++) { if (grid[i][j] == 1) { cnt++; dfs(i, j, grid, cnt); pts.insert(norm(m[cnt])); } } } return pts.size(); } }; main(){ Solution ob; vector<vector<int>> v = {{1,1,0,0,0},{1,0,0,0,0},{0,0,0,0,1},{0,0,0,1,1}}; cout << (ob.numDistinctIslands2(v)); }
ইনপুট
{{1,1,0,0,0},{1,0,0,0,0},{0,0,0,0,1},{0,0,0,1,1}}
আউটপুট
1
