数据结构
网络
关系数据库管理系统
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
时尚研究
法律研究在 C++ 中创建大型岛屿
假设我们有一个二维网格，其中包含二进制值（0 和 1），我们最多可以将一个 0 更改为 1。之后，我们必须找到最大岛屿的大小？这里，岛屿是 1 的一个 4 个方向（上、下、左、右）连接的组。
因此，如果输入类似于 [[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 的数组 area
n := 网格的行数，m := 网格的列数
初始化 i := 0，当 i < n 时，更新（将 i 增加 1），执行 -
初始化 j := 0，当 j < m 时，更新（将 j 增加 1），执行 -
如果 grid[i, j] 等于 1，则 -
将 dfs(grid, i, j, idx) 插入 area 的末尾
ret := ret 和 area 的最后一个元素的最大值
（将 idx 增加 1）
初始化 i := 0，当 i < n 时，更新（将 i 增加 1），执行 -
如果 grid[i, j] 等于 0，则 -
定义一个集合 idxs
初始化 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 中的所有元素 it，执行 -
temp := temp + area[it]
（将 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
202 次查看
