C++ में एन्क्लेव्स की संख्या (Number of Enclaves)

मान लीजिए हमें एक 2D ऐरे A दिया गया है, जहां प्रत्येक सेल 0 (समुद्र दर्शाता है) या 1 (भूमि दर्शाता है) है। यहां एक चाल में एक भूमि वर्ग से 4-दिशात्मक रूप से दूसरे भूमि वर्ग पर चलना, या ग्रिड की सीमा से बाहर निकलना शामिल है। हमें ग्रिड में उन भूमि वर्गों की संख्या खोजनी है जिनसे हम किसी भी संख्या में चालों में ग्रिड की सीमा से बाहर नहीं निकल सकते।

उदाहरण के लिए, यदि ग्रिड है:

समाधान दृष्टिकोण

1. दिशा ऐरे dir := [[1,0], [-1,0], [0,1], [0,-1]] बनाएं

2. dfs() विधि बनाएं जो x, y और मैट्रिक्स A लेती है

3. सीमा पर स्थित सभी भूमि सेल्स से DFS चलाकर उन्हें 0 में बदलें

4. शेष बचे 1s की गिनती करें - वही एन्क्लेव्स हैं

C++ कार्यान्वयन

#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>>& A){ 
        if(x < 0 || y < 0 || x >= A.size() || y >= A[0].size() || A[x][y] == 0) return; 
        A[x][y] = 0; 
        for(int k = 0; k < 4; k++){ 
            int nx = dir[k][0] + x; 
            int ny = dir[k][1] + y; 
            dfs(nx, ny, A); 
        } 
    } 
    
    int numEnclaves(vector<vector<int>>& A) { 
        int ret = 0; 
        int n = A.size(); 
        int m = n ? A[0].size() : 0; 
        for(int i = 0; i < n; i++){ 
            if(A[i][0] == 1) dfs(i, 0, A); 
            if(A[i][m - 1] == 1) dfs(i, m - 1, A); 
        } 
        for(int i = 0; i < m; i++){ 
            if(A[0][i] == 1) dfs(0, i, A); 
            if(A[n - 1][i] == 1) dfs(n - 1, i, A); 
        } 
        for(int i = 0; i < n; i++){ 
            for(int j = 0; j < m; j++){ 
                ret += A[i][j]; 
            } 
        } 
        return ret; 
    } 
}; 

int main(){ 
    vector<vector<int>> v1 = {{0,0,0,0},{1,0,1,0},{0,1,1,0},{0,0,0,0}}; 
    Solution ob; 
    cout << (ob.numEnclaves(v1)); 
    return 0; 
}

इनपुट

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

आउटपुट

3