C++で大きな島を作る

バイナリ値（0と1）の2Dグリッドがあるとすると、最大で1つの0を1に変更します。その後、最大の島のサイズを見つける必要があります。 ？ここで、島は4方向（上、下、左、右）に接続された1のグループです。

したがって、入力が[[1、0]、[0、1]]の場合、出力は3になります。これは、1つの0を1に変更し、2つの1を接続すると、次のような島が得られるためです。面積=3。

これを解決するには、次の手順に従います-

• サイズの配列dirを定義します：4 x 2、dir：={{1、0}、{-1、0}、{0、1}、{0、-1}}

• 関数dfs（）を定義します。これには、idx、i、j、グリッドが必要です。

• （i、j）がグリッド領域内にあり、grid [i、j]が1に等しくない場合、-

  • 0を返す

• ret：=1

• grid [i、j]：=idx

• 初期化k：=0の場合、k <4の場合、更新（kを1増やします）、実行-

  • ni：=dir [k、0] + i、nj：=dir [k、1] + j

  • ret：=ret + dfs（grid、ni、nj、idx）

• retを返す

• メインの方法から、次のようにします-

• 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と同じ場合、-

    • 1つのセットIDXを定義する

    • 初期化k：=0の場合、k <4の場合、更新（kを1増やします）、実行-

      • ni：=i + dir [k、0]、nj：=j + dir [k、1]

      • グリッドの範囲内のni、njの場合、-

        • grid [ni、nj]がゼロ以外の場合、-

          • grid [ni、nj]をidxsに挿入します

    • temp：=1

    • idxs内のすべての要素について、次のようにします-

      • temp：=temp + area [it]

      • （1ずつ増やします）p + area [it]

  • ret：=retとtempの最大値

• retを返す

理解を深めるために、次の実装を見てみましょう-

例

#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