C++ में बंद द्वीपों की संख्या

मान लीजिए हमारे पास एक 2D ग्रिड है जिसमें 0 (भूमि के रूप में) और 1 (पानी के रूप में) होते हैं। एक द्वीप 0 का एक अधिकतम 4-दिशात्मक जुड़ा हुआ समूह है। एक बंद द्वीप वह द्वीप है जो पूरी तरह से 1 से घिरा हुआ है। हमें बंद द्वीपों की संख्या ढूंढनी होगी। इसलिए यदि ग्रिड इस तरह है:

इसलिए आउटपुट 2 होगा। दो द्वीप हैं, जो पूरी तरह से पानी से घिरे हुए हैं।

इसे हल करने के लिए, हम इन चरणों का पालन करेंगे:

• एक फ्लैग वेरिएबल परिभाषित करें

• एक dfs विधि परिभाषित करें, यह ग्रिड, i, j, n और m लेगा

• यदि i और j ग्रिड की सीमा के अंदर नहीं हैं, तो फ्लैग := false सेट करें और लौटें

• यदि g[i,j] = 1 या g[i, j] = -1 है, तो लौटें

• यदि g[i, j] = 0 है, तो g[i, j] = -1

• dfs(g, i + 1, j, n, m), dfs(g, i, j+1, n, m), dfs(g, i - 1, j, n, m), dfs(g, i, j-1, n, m) कॉल करें

• मुख्य विधि इस तरह होगी:

• n x m क्रम का एक dp मैट्रिक्स बनाएं, और इसे -1 से भरें

• i को 0 से n - 1 तक के लिए

  • j को 0 से m - 1 तक के लिए

    • यदि g[i, j] = 0 है, तो

      • फ्लैग := true

      • dfs(g, i, j, n, m)

      • फ्लैग := true

      • ans := ans + फ्लैग

• ans लौटाएं

बेहतर समझ के लिए निम्नलिखित कार्यान्वयन देखें:

उदाहरण

#include <bits/stdc++.h>
using namespace std;

class Solution {
public:
    vector < vector <int> > dp;
    bool flag;
    void dfs(vector<vector<int>>& g, int i, int j, int n, int m) {
        if(i >= n || j >= m || i < 0 || j < 0) {
            flag = false;
            return;
        }
        if(g[i][j] == 1 || g[i][j] == -1) return;
        if(g[i][j] == 0) g[i][j] = -1;
        dfs(g, i+1, j, n, m);
        dfs(g, i, j+1, n, m);
        dfs(g, i-1, j, n, m);
        dfs(g, i, j-1, n, m);
    }
    int closedIsland(vector<vector<int>>& g) {
        int ans = 0;
        int n = g.size();
        int m = g[0].size();
        dp = vector < vector <int> > (n, vector <int> (m, -1));
        for(int i = 0; i < n; i++) {
            for(int j = 0; j < m; j++) {
                if(g[i][j] == 0) {
                    flag = true;
                    dfs(g, i, j, n, m);
                    ans += flag;
                }
            }
        }
        return ans;
    }
};

int main() {
    vector<vector<int>> v = 
    {{1,1,1,1,1,1,1,0},{1,0,0,0,0,1,1,0},{1,0,1,0,1,1,1,0},{1,0,0,0,0,1,0,1},{1,1,1,1,1,1,1,0}};
    Solution ob;
    cout << (ob.closedIsland(v));
}

इनपुट

[[1,1,1,1,1,1,1,0],[1,0,0,0,0,1,1,0],[1,0,1,0,1,1,1,0],[1,0,0,0,0,1,0,1],[1,1,1,1,1,1,1,0]]

आउटपुट

2