C++로 큰 섬 만들기

이진 값(0과 1)의 2D 그리드가 있다고 가정하고 최대 하나의 0을 1로 변경합니다. 그 후 가장 큰 섬의 크기를 찾아야 합니다. ? 여기서 섬은 4방향(위, 아래, 왼쪽, 오른쪽)으로 연결된 1 그룹입니다.

따라서 입력이 [[1, 0], [0, 1]]과 같으면 출력은 3이 됩니다. 이는 하나의 0을 1로 변경하고 두 개의 1을 연결하면 다음과 같은 섬을 얻을 수 있기 때문입니다. 면적 =3.

이 문제를 해결하기 위해 다음 단계를 따릅니다. −

배열 dir 크기 정의:4 x 2, dir :={{1, 0}, { - 1, 0}, {0, 1}, {0, - 1}}
dfs() 함수를 정의하면 idx, i, j, grid,
가 필요합니다.
(i,j)가 그리드 영역 안에 있고 grid[i, j]가 1과 같지 않으면 -
- 0 반환
렛 :=1
그리드[i, j] :=idx
초기화 k :=0의 경우 k <4일 때 업데이트(k를 1만큼 증가), −
- ni :=dir[k, 0] + i, nj :=dir[k, 1] + j
- ret :=ret + dfs(그리드, ni, nj, idx)
리턴 렛
기본 방법에서 다음을 수행하십시오 -
ret :=0, idx :=2
크기가 2인 배열 영역 정의
n :=그리드의 행 개수, m :=그리드의 열 개수
initialize i :=0의 경우, i
- j 초기화의 경우:=0, j
  - grid[i, j]가 1과 같으면 -
    - 영역 끝에 dfs(grid, i, j, idx) 삽입
    - ret :=ret의 최대값과 영역의 마지막 요소
    - (idx를 1씩 증가)
initialize i :=0의 경우, i
- grid[i, j]가 0과 같으면 -
  - 하나의 세트 idx 정의
  - 초기화 k :=0의 경우 k <4일 때 업데이트(k를 1만큼 증가), −
    - ni :=i + dir[k, 0],nj :=j + dir[k, 1]
    - 그리드 범위에 ni,nj이면 -
      - grid[ni, nj]가 0이 아니면 -
        
        그리드[ni, nj]를 idxs
        에 삽입
  - 온도 :=1
  - idxs의 모든 요소에 대해 다음을 수행합니다. -
    - 온도 :=온도 + 면적[it]
    - (1)p + area[it]
      만큼 증가
- 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}}