用C ++打造大岛

假设我们有一个二进制值（0s和1s）的2D网格，我们最多将0更改为1。之后，我们必须找出最大的岛的大小是多少？在这里，一个岛是一个4方向（上，下，左，右）连接的1s组。

因此，如果输入类似于[[1，0]，[0，1]]，则输出将为3，这是因为如果我们将0更改为1并连接两个1，则将得到一个孤岛面积= 3。

为了解决这个问题，我们将遵循以下步骤-

• 定义大小为4 x 2的数组dir，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 <n时，更新（将i增加1），执行-

• 如果grid [i，j]与1相同，则-

• 在区域末尾插入dfs(grid,i,j,idx)

• ret：= ret的最大值和区域的最后一个元素

• （将idx增加1）

• 对于初始化j：= 0，当j <m时，更新（将j增加1），执行-

• 对于初始化i：= 0，当i <n时，更新（将i增加1），执行-

• 定义一组IDX

• 对于初始化k：= 0，当k <4时，更新（将k增加1），执行-

• 温度：= 1

• 对于idxs中的所有元素，请执行以下操作-

• 如果grid [ni，nj]不为零，则-

• 将grid [ni，nj]插入idxs

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

• 如果ni，nj在网格范围内，则-

• temp：= temp + area [it]

• （增加1）p +面积[it]

• 如果grid [i，j]等于0，则-

• 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