मान लीजिए हमारे पास एक बाइनरी 2D ऐरे ग्रिड है, यहां एक द्वीप 1's (भूमि) का एक समूह है जो 4-दिशात्मक रूप से जुड़ा हुआ है (क्षैतिज या लंबवत)। हम मान सकते हैं कि ग्रिड के चारों किनारे पानी से घिरे हैं। हमें विशिष्ट द्वीपों की संख्या गिननी है।
एक द्वीप को दूसरे के समान माना जाता है जब एक द्वीप को अनुवादित करके (घुमाए या प्रतिबिंबित किए बिना) दूसरे के बराबर बनाया जा सकता है।
उदाहरण के लिए, यदि इनपुट ग्रिड है:
| 1 | 1 | 0 | 1 | 1 |
| 1 | 0 | 0 | 0 | 0 |
| 0 | 0 | 0 | 0 | 1 |
| 1 | 1 | 0 | 1 | 1 |
तो आउटपुट 3 होगा।
हल करने की विधि
हम DFS का उपयोग करके प्रत्येक द्वीप के आकार को एक स्ट्रिंग के रूप में एनकोड करेंगे:
dfs()फ़ंक्शन परिभाषित करें जो x, y, ग्रिड, अस्थायी स्ट्रिंग, और दिशा वर्ण लेता है।- यदि सीमा से बाहर या पानी है, तो लौटें।
- ग्रिड[x][y] = 0 सेट करें (देखा गया चिह्नित करें)।
- दिशा वर्ण को अस्थायी स्ट्रिंग में जोड़ें।
- चार दिशाओं में रिकर्सिवली कॉल करें: दाएं (r), बाएं (l), नीचे (d), ऊपर (u)।
- बैकट्रैकिंग के लिए 'b' जोड़ें।
- मुख्य विधि में:
- ret = 0, visited सेट परिभाषित करें।
- प्रत्येक सेल के लिए, यदि भूमि है, तो खाली स्ट्रिंग aux से dfs शुरू करें।
- यदि aux visited में नहीं है, तो ret बढ़ाएं और visited में डालें।
- ret लौटाएं।
उदाहरण
बेहतर समझ के लिए निम्न कार्यान्वयन देखें:
#include <bits/stdc++.h> using namespace std; int dir[4][2] = {{1, 0}, {-1, 0}, {0, -1}, {0, 1}}; class Solution { public: void dfs(int x, int y, vector < vector <int> >& grid, string& temp, char c){ if (x < 0 || y < 0 || x >= grid.size() || y >= grid[0].size() || !grid[x][y]) return; grid[x][y] = 0; temp += c; dfs(x + 1, y, grid, temp, 'r'); dfs(x - 1, y, grid, temp, 'l'); dfs(x, y + 1, grid, temp, 'd'); dfs(x, y - 1, grid, temp, 'u'); temp += 'b'; } int numDistinctIslands(vector<vector<int>>& grid) { int ret = 0; set<string> visited; for (int i = 0; i < grid.size(); i++) { for (int j = 0; j < grid[0].size(); j++) { if (grid[i][j]) { string aux = ""; dfs(i, j, grid, aux, 's'); if (!visited.count(aux)) { ret++; visited.insert(aux); } } } } return ret; } }; main(){ Solution ob; vector<vector<int>> v = {{1,1,0,1,1},{1,0,0,0,0},{0,0,0,0,1},{1,1,0,1,1}}; cout<<(ob.numDistinctIslands(v)); }
इनपुट
{{1,1,0,1,1},{1,0,0,0,0},{0,0,0,0,1},{1,1,0,1,1}}
आउटपुट
3
