การสร้างเกาะขนาดใหญ่ที่สุดใน C++

สมมติว่าเรามีกริด 2D ของค่าบайนารี (0 และ 1) เราสามารถเปลี่ยน 0 สูงสุดหนึ่งตัวเป็น 1 หลังจากนั้นเราต้องหาว่าขนาดของเกาะที่ใหญ่ที่สุดคือเท่าไร เกาะคือกลุ่มของ 1 ที่เชื่อมต่อกันใน 4 ทิศทาง (บน, ล่าง, ซ้าย, ขวา)

เช่น หากอินพุตคือ [[1, 0], [0, 1]] เอาต์พุตจะเป็น 3 เพราะถ้าเราเปลี่ยน 0 หนึ่งตัวเป็น 1 และเชื่อมสอง 1 เข้าด้วยกัน จะได้เกาะที่มีพื้นที่ = 3

เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอน −

• กำหนดอาร์เรย์ dir ขนาด 4x2 สำหรับ 4 ทิศทาง

• กำหนดฟังก์ชัน dfs() สำหรับค้นหาเกาะและกำหนดหมายเลขให้แต่ละเกาะ

• จากเมธอดหลัก วนลูปหาเกาะทั้งหมด คำนวณพื้นที่เก็บในอาร์เรย์ area

• วนลูปหา 0 ทุกตัว ลองเปลี่ยนเป็น 1 คำนวณพื้นที่เกาะที่รวมกันได้

• คืนค่าพื้นที่สูงสุด

ลองดูการนำไปใช้ −

ตัวอย่าง

#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; 
                    set <int> :: iterator it = idxs.begin(); 
                    while(it != idxs.end()){ 
                        temp += area[*it]; 
                        it++; 
                    } 
                    ret = max(ret, temp); 
                } 
            } 
        } 
        return ret; 
    } 
}; 

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

อินพุต

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

เอาต์พุต

3