用C ++打造大岛
因此，如果输入类似于[[1，0]，[0，1]]，则输出将为3，这是因为如果我们将0更改为1并连接两个1，则将得到一个孤岛面积=3。
为了解决这个问题，我们将遵循以下步骤-
定义大小为4x2的数组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