C++-এ একটি ০ কে ১ এ পরিবর্তন করে সর্বোচ্চ দ্বীপ (Largest Island) বের করা

ধরুন আমাদের একটি ২D গ্রিড দেওয়া আছে যাতে শুধু ০ এবং ১ রয়েছে। আমরা শুধু একটি ০ কে ১ এ পরিবর্তন করতে পারি। এর পর আমাদের জানতে হবে সর্বোচ্চ দ্বীপের আকার কত। এখানে দ্বীপ বলতে ৪-দিকের (উপর, নিচ, বাম, ডান) সংযুক্ত ১-গুলোর গোষ্ঠী বোঝায়।

উদাহরণ

ইনপুট: [[1, 0], [0, 1]] → আউটপুট: 3

ব্যাখ্যা: একটি ০ কে ১ এ পরিবর্তন করলে দুটি ১ সংযুক্ত হয়ে ৩ আকারের একটি দ্বীপ তৈরি হয়।

সমাধানের ধাপসমূহ

DFS ব্যবহার করে প্রতিটি বিদ্যমান দ্বীপের আকার বের করুন এবং প্রতিটি দ্বীপকে একটি অনন্য আইডি দিন।
প্রতিটি ০ সেলের জন্য, তার ৪-দিকের প্রতিবেশী দ্বীপগুলোর আইডি সংগ্রহ করুন।
সেটি ১ এ পরিবর্তন করলে তৈরি হওয়া দ্বীপের আকার = ১ + সংযুক্ত দ্বীপগুলোর আকারের যোগফল।
সর্বোচ্চ আকারটি রিটার্ন করুন।

প্রোগ্রাম উদাহরণ

#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++;
                }
            }
        }
        
        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 (auto it = idxs.begin(); it != idxs.end(); it++) {
                        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));
}

ইনপুট

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