C++ में एक बड़ा द्वीप बनाना (Making A Large Island) - ग्रिड में अधिकतम द्वीप क्षेत्रफल

समस्या विवरण

हमें एक 2D ग्रिड दिया गया है जिसमें बाइनरी मान (0 और 1) हैं। हम अधिकतम एक 0 को 1 में बदल सकते हैं। उसके बाद हमें सबसे बड़े द्वीप (island) का आकार ज्ञात करना है। यहां द्वीप 4-दिशात्मक रूप से (ऊपर, नीचे, बाएं, दाएं) जुड़े 1s का समूह है।

उदाहरण

इनपुट

{{1, 0}, {0, 1}}

आउटपुट

व्याख्या

यदि हम एक 0 को 1 में बदलकर दो 1s को जोड़ते हैं, तो हमें क्षेत्रफल 3 का द्वीप मिलता है।

समाधान दृष्टिकोण (DFS + घटक लेबलिंग)

DFS का उपयोग करके प्रत्येक द्वीप को एक अद्वितीय सूचकांक (index ≥ 2) से लेबल करें और उसका क्षेत्रफल रिकॉर्ड करें।
प्रत्येक 0 सेल के लिए, उसके 4 पड़ोसियों की जांच करें। अद्वितीय पड़ोसी द्वीप सूचकांकों को एकत्र करें।
उस 0 को 1 में बदलने पर नया क्षेत्रफल = 1 + उन अद्वितीय द्वीपों के क्षेत्रफलों का योग।
सभी 0 सेल्स के लिए अधिकतम क्षेत्रफल लौटाएं।

कार्यकारी प्रोग्राम

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

int dir[4][2] = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};

class Solution {
public:
    int dfs(vector<vector<int>>& grid, int i, int j, int idx) {
        if (i < 0 || j < 0 || i >= grid.size() || j >= grid[0].size() || grid[i][j] != 1)
            return 0;
        int ret = 1;
        grid[i][j] = idx;
        for (int k = 0; k < 4; k++) {
            int ni = dir[k][0] + i;
            int nj = dir[k][1] + j;
            ret += dfs(grid, ni, nj, idx);
        }
        return ret;
    }
    
    int largestIsland(vector<vector<int>>& grid) {
        int ret = 0;
        int idx = 2;
        vector<int> area(2);
        int n = grid.size();
        int m = grid[0].size();
        
        // सभी द्वीपों को लेबल करें और क्षेत्रफल रिकॉर्ड करें
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                if (grid[i][j] == 1) {
                    area.push_back(dfs(grid, i, j, idx));
                    ret = max(ret, area.back());
                    idx++;
                }
            }
        }
        
        // प्रत्येक 0 को 1 में बदलने का प्रयास करें
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                if (grid[i][j] == 0) {
                    set<int> idxs;
                    for (int k = 0; k < 4; k++) {
                        int ni = i + dir[k][0];
                        int nj = j + dir[k][1];
                        if (ni < 0 || nj < 0 || ni >= grid.size() || nj >= grid[0].size()) continue;
                        if (grid[ni][nj]) {
                            idxs.insert(grid[ni][nj]);
                        }
                    }
                    int temp = 1;
                    for (int it : idxs) {
                        temp += area[it];
                    }
                    ret = max(ret, temp);
                }
            }
        }
        return ret;
    }
};

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