मान लीजिए कि हमारे पास एक गैर-रिक्त 2D बाइनरी सरणी है जिसे ग्रिड कहा जाता है, यहां एक द्वीप 1 (भूमि का प्रतिनिधित्व करने वाला) का एक समूह है जो 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
. होगाइसे हल करने के लिए, हम इन चरणों का पालन करेंगे -
-
एक नक्शा परिभाषित करें मी
-
फ़ंक्शन dfs() को परिभाषित करें, इसमें i, j, ग्रिड, idx,
. लगेगा -
अगर i और j ग्रिड की रेंज में हैं और ग्रिड[i,j] 0 है तो -
-
वापसी
-
-
ग्रिड [i, j] :=0
-
m[idx]
. के अंत में { i, j } डालें -
dfs(i + 1, j, ग्रिड, idx)
-
dfs(i-1, j, grid, idx)
-
dfs(i, j-1, grid, idx)
-
dfs(i, j + 1, ग्रिड, idx)
-
एक फ़ंक्शन मानदंड () को परिभाषित करें, यह एक सरणी v
. लेगा-
8 पंक्तियों के साथ जोड़े के एक 2D सरणी को परिभाषित करें
-
इनिशियलाइज़ i:=0 के लिए, जब i
-
x :=v[i].पहले
-
y :=v[i].सेकंड
-
s[0]
. के अंत में { x, y } डालें -
s[1] के अंत में { x, -y } डालें [1]
-
s[2] के अंत में { - x, y } डालें [2]
-
s[3]
. के अंत में {- x, -y} डालें -
s[4]
. के अंत में { y, x } डालें -
s[5]
. के अंत में { y, -x } डालें -
s[6]
. के अंत में {- y, x } डालें -
s[7]
. के अंत में {- y, -x } डालें
-
-
इनिशियलाइज़ करने के लिए:=0, जब i <साइज़ ऑफ़ s, अपडेट (i से 1 तक बढ़ाएँ), करें -
-
सरणी s[i]
को क्रमबद्ध करें
-
-
इनिशियलाइज़ करने के लिए:=0, जब i <साइज़ ऑफ़ s, अपडेट (i से 1 तक बढ़ाएँ), करें -
-
इनिशियलाइज़ j :=1 के लिए, जब j
-
s[i, j].पहला :=s[i, j].first - s[i, 0].first
-
s[i, j].second :=s[i, j].second - s[i, 0].second
-
-
एस [i, 0]। पहला:=0
-
s[i, 0].सेकंड :=0
-
-
सरणी को क्रमबद्ध करें
-
वापसी s[0]
-
-
मुख्य विधि से निम्न कार्य करें -
-
एक सेट अंक परिभाषित करें
-
सीएनटी:=1
-
प्रारंभ करने के लिए i:=0, जब i <ग्रिड का आकार, अद्यतन (i से 1 तक बढ़ाएँ), करें -
-
प्रारंभ करने के लिए j :=0, जब j <ग्रिड का आकार [0], अद्यतन करें (1 से j बढ़ाएँ), &miuns;
करें-
अगर ग्रिड [i, j] 1 के समान है, तो -
-
(cnt 1 से बढ़ाएँ)
-
dfs(i, j, grid, cnt)
-
पीटी में मानदंड (एम [सीएनटी]) डालें
-
-
-
-
अंकों का वापसी आकार
आइए बेहतर समझ पाने के लिए निम्नलिखित कार्यान्वयन देखें -
उदाहरण
#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