資料結構
網路
關係資料庫管理系統
作業系統
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 次檢視
