Tạo một hòn đảo lớn trong C ++

Giả sử chúng ta có một lưới 2D gồm các giá trị nhị phân (0 và 1), chúng ta thay đổi nhiều nhất từ 0 đến 1. Sau đó, chúng ta phải tìm kích thước của hòn đảo lớn nhất. ? Đây là một hòn đảo là một nhóm 1 được kết nối 4 hướng (trên, dưới, trái, phải).

Vì vậy, nếu đầu vào giống như [[1, 0], [0, 1]], thì đầu ra sẽ là 3, điều này là do nếu chúng ta thay đổi một 0 thành 1 và kết nối hai số 1, thì chúng ta sẽ nhận được một đảo với diện tích =3.

Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -

Xác định dir mảng có kích thước:4 x 2, dir:={{1, 0}, {- 1, 0}, {0, 1}, {0, - 1}}
Xác định một hàm dfs (), hàm này sẽ lấy idx, i, j, lưới,
nếu (i, j) nằm trong vùng lưới và lưới [i, j] không bằng 1, thì -
- trả về 0
ret:=1
lưới [i, j]:=idx
để khởi tạo k:=0, khi k <4, cập nhật (tăng k lên 1), thực hiện -
- ni:=dir [k, 0] + i, nj:=dir [k, 1] + j
- ret:=ret + dfs (lưới, ni, nj, idx)
trả lại ret
Từ phương thức chính, thực hiện như sau -
ret:=0, idx:=2
Xác định một vùng có kích thước 2
n:=Số hàng của lưới, m:=số cột của lưới
để khởi tạo i:=0, khi i
- để khởi tạo j:=0, khi j
  - nếu lưới [i, j] giống 1, thì -
    - chèn dfs (lưới, i, j, idx) vào cuối vùng
    - ret:=tối đa ret và phần tử cuối cùng của khu vực
    - (tăng idx lên 1)
để khởi tạo i:=0, khi i
- nếu lưới [i, j] giống 0, thì -
  - Xác định một bộ idxs
  - để khởi tạo k:=0, khi k <4, cập nhật (tăng k lên 1), thực hiện -
    - ni:=i + dir [k, 0], nj:=j + dir [k, 1]
    - nếu ni, nj trong phạm vi lưới, thì -
      - nếu lưới [ni, nj] khác 0 thì -
        
        chèn lưới [ni, nj] vào idxs
  - tạm thời:=1
  - đối với tất cả các phần tử nó trong idxs, do -
    - temp:=temp + area [it]
    - (tăng nó lên 1) p + area [it]
- ret:=tối đa ret và tạm thời
trả lại ret

Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn -

Ví dụ

#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));
}

Đầu vào

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

Tạo một hòn đảo lớn trong C ++

Ví dụ

Đầu vào

Đầu ra