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

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

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

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

• กำหนดอาร์เรย์ dir ขนาด:4 x 2, dir :={{1, 0}, { - 1, 0}, {0, 1}, {0, - 1}}

• กำหนดฟังก์ชัน dfs() ซึ่งจะใช้ idx, i, j, กริด

• ถ้า (i,j) อยู่ภายในขอบเขตกริดและกริด[i, j] ไม่เท่ากับ 1 ดังนั้น −

  • คืนค่า 0

• ยกเลิก :=1

• กริด[i, j] :=idx

• สำหรับการเริ่มต้น k :=0 เมื่อ k <4 อัปเดต (เพิ่ม k ขึ้น 1) ทำ -

  • พรรณี :=dir[k, 0] + i, nj :=dir[k, 1] + j

  • ret :=ret + dfs(grid, ni, nj, idx)

• รีเทิร์น

• จากวิธีหลัก ให้ทำดังนี้ −

• ret :=0, idx :=2

• กำหนดพื้นที่อาร์เรย์ขนาด 2

• n :=จำนวนแถวของตาราง m :=จำนวนคอลัมน์ของกริด

• สำหรับการเริ่มต้น i :=0 เมื่อ i

  • สำหรับการเริ่มต้น j :=0 เมื่อ j

    • ถ้า grid[i, j] เหมือนกับ 1 แล้ว −

      • แทรก dfs(grid, i, j, idx) ที่ส่วนท้ายของพื้นที่

      • ret :=สูงสุดของ ret และองค์ประกอบสุดท้ายของพื้นที่

      • (เพิ่ม idx ขึ้น 1)

• สำหรับการเริ่มต้น i :=0 เมื่อ i

  • ถ้า grid[i, j] เท่ากับ 0 แล้ว −

    • กำหนด idxs หนึ่งชุด

    • สำหรับการเริ่มต้น k :=0 เมื่อ k <4 อัปเดต (เพิ่ม k ขึ้น 1) ทำ -

      • พรรณี :=i + dir[k, 0],nj :=j + dir[k, 1]

      • ถ้า ni,nj อยู่ในช่วงของกริด ดังนั้น −

        • ถ้า grid[ni, nj] ไม่ใช่ศูนย์ ดังนั้น −

          • แทรกกริด[ni, nj] ลงใน idxs

    • อุณหภูมิ :=1

    • สำหรับองค์ประกอบทั้งหมดใน idxs ให้ทำ -

      • อุณหภูมิ :=อุณหภูมิ + พื้นที่[มัน]

      • (เพิ่มขึ้น 1)p + พื้นที่[มัน]

  • ret :=สูงสุดของ ret และ temp

• รีเทิร์น

ให้เราดูการใช้งานต่อไปนี้เพื่อความเข้าใจที่ดีขึ้น -

ตัวอย่าง

#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