मान लीजिए हमारे पास grid नामक एक नॉन-खाली 2D बाइनरी ऐरे है, यहां एक द्वीप 1's (भूमि दर्शाने वाले) का एक समूह है जो 4-दिशात्मक रूप से जुड़े हुए हैं। हम यह भी मान सकते हैं कि ग्रिड के चारों किनारे पानी से घिरे हुए हैं।
हमें विशिष्ट द्वीपों की संख्या गिननी है। एक द्वीप को दूसरे के समान माना जाता है यदि उनका आकार समान है, या 90, 180, या 270 डिग्री के रोटेशन के बाद या लेफ्ट/राइट दिशा या अप/डाउन दिशा के रिफ्लेक्शन के बाद उनका आकार समान है।
तो, यदि इनपुट है:
| 1 | 1 | 0 | 0 | 0 |
| 1 | 0 | 0 | 0 | 0 |
| 0 | 0 | 0 | 0 | 1 |
| 0 | 0 | 0 | 1 | 1 |
तो आउटपुट 1 होगा।
इसे हल करने के लिए, हम इन चरणों का पालन करेंगे:
एक मैप m परिभाषित करें
एक फ़ंक्शन dfs() परिभाषित करें, जो i, j, grid, idx लेगा,
यदि i और j ग्रिड की रेंज में हैं और grid[i,j] 0 है तो:
लौटें
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 लेगा
8 पंक्तियों वाला पेयर्स का एक 2D ऐरे s परिभाषित करें
i := 0 से शुरू करें, जब i < v का आकार, अपडेट करें (i को 1 से बढ़ाएं), करें:
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 को 1 से बढ़ाएं), करें:
ऐरे s[i] को सॉर्ट करें
i := 0 से शुरू करें, जब i < s का आकार, अपडेट करें (i को 1 से बढ़ाएं), करें:
j := 1 से शुरू करें, जब j < v का आकार, अपडेट करें (j को 1 से बढ़ाएं), करें:
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 को 1 से बढ़ाएं), करें:
j := 0 से शुरू करें, जब j < grid[0] का आकार, अपडेट करें (j को 1 से बढ़ाएं), करें:
यदि grid[i, j], 1 के समान है, तो:
(cnt को 1 से बढ़ाएं)
dfs(i, j, grid, cnt)
norm(m[cnt]) को pts में डालें
pts का आकार लौटाएं
बेहतर समझ के लिए निम्नलिखित कार्यान्वयन देखें:
उदाहरण
#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
map>> m;
void dfs(int i, int j, vector>& 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> norm(vector> v) {
vector>> 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>& grid) {
set>> 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();
}
};
int main() {
Solution ob;
vector> 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
