孤岛的总面积
101. 孤岛的总面积 (kamacoder.com)
#include<iostream>
#include<vector>using namespace std;int times = 0;inline bool valid(int i, int j, const int &m, const int &n){return i >= 0 && i < n && j >= 0 && j < m;
}void dfs(int i, int j, vector<vector<int>>& isVisited, vector<vector<int>> &island, const int &n,const int &m){isVisited[i][j] = 1;island[i][j] = 0;times++;if(valid(i, j + 1, m, n) && island[i][j + 1] == 1 && isVisited[i][j + 1] == 0){dfs(i, j + 1, isVisited, island, n, m);}if(valid(i + 1, j, m, n) && island[i + 1][j] == 1 && isVisited[i + 1][j] == 0){dfs(i + 1, j, isVisited, island, n, m);}if(valid(i - 1, j, m, n) && island[i - 1][j] == 1 && isVisited[i - 1][j] == 0){dfs(i - 1, j, isVisited, island, n, m);}if(valid(i, j - 1, m, n) && island[i][j - 1] == 1 && isVisited[i][j - 1] == 0){dfs(i, j - 1, isVisited, island, n, m);}
}int main(){int n = 0, m = 0;cin >> n >> m;vector<vector<int>> island(n, vector<int>(m, 0));for(int i = 0; i < n; i++){for(int j = 0; j < m; j++){cin >> island[i][j];}}int ans = 0;vector<vector<int>> isVisited(n, vector<int>(m, 0));for(int i = 0; i < n; i++){if(island[i][0] == 1){dfs(i, 0, isVisited, island, n, m);}if(island[i][m - 1] == 1){dfs(i, m - 1, isVisited, island, n, m);}}for(int j = 0; j < m; j++){if(island[0][j] == 1){dfs(0, j, isVisited, island, n, m);}if(island[n - 1][j] == 1){dfs(n - 1, j, isVisited, island, n, m);}}times = 0;for(int i = 0; i < n; i++){for(int j = 0; j < m; j++){if(island[i][j] == 1 && isVisited[i][j] == 0){dfs(i, j, isVisited, island, n, m);}}}cout << times << endl;
}沉没孤岛
#include<iostream>
#include<vector>using namespace std;int times = 0;inline bool valid(int i, int j, const int &m, const int &n){return i >= 0 && i < n && j >= 0 && j < m;
}void dfs(int i, int j, vector<vector<int>>& isVisited, vector<vector<int>> &island, const int &n,const int &m){isVisited[i][j] = 1;island[i][j] = 2;times++;if(valid(i, j + 1, m, n) && island[i][j + 1] == 1 && isVisited[i][j + 1] == 0){dfs(i, j + 1, isVisited, island, n, m);}if(valid(i + 1, j, m, n) && island[i + 1][j] == 1 && isVisited[i + 1][j] == 0){dfs(i + 1, j, isVisited, island, n, m);}if(valid(i - 1, j, m, n) && island[i - 1][j] == 1 && isVisited[i - 1][j] == 0){dfs(i - 1, j, isVisited, island, n, m);}if(valid(i, j - 1, m, n) && island[i][j - 1] == 1 && isVisited[i][j - 1] == 0){dfs(i, j - 1, isVisited, island, n, m);}
}int main(){int n = 0, m = 0;cin >> n >> m;vector<vector<int>> island(n, vector<int>(m, 0));for(int i = 0; i < n; i++){for(int j = 0; j < m; j++){cin >> island[i][j];}}int ans = 0;vector<vector<int>> isVisited(n, vector<int>(m, 0));for(int i = 0; i < n; i++){if(island[i][0] == 1){dfs(i, 0, isVisited, island, n, m);}if(island[i][m - 1] == 1){dfs(i, m - 1, isVisited, island, n, m);}}for(int j = 0; j < m; j++){if(island[0][j] == 1){dfs(0, j, isVisited, island, n, m);}if(island[n - 1][j] == 1){dfs(n - 1, j, isVisited, island, n, m);}}times = 0;for(int i = 0; i < n; i++){for(int j = 0; j < m; j++){if(island[i][j] == 1){island[i][j] = 0;}}}for(int i = 0; i < n; i++){for(int j = 0; j < m; j++){if(island[i][j] == 2){island[i][j] = 1;}}}for(int i = 0; i < n; i++){for(int j = 0; j < m; j++){cout << island[i][j] << " ";}cout << endl;}
}103.水流问题
#include <iostream>
#include <vector>using namespace std;
vector<vector<int>> result;void dfs(int flag, int i, int j, vector<vector<int>> &visited, vector<vector<int>> &island, const int &n, const int &m){visited[i][j] = 1;if(i + 1 < n && visited[i + 1][j] != 1 && island[i + 1][j] >= island[i][j]){dfs(flag, i + 1, j, visited, island, n , m);}if(j + 1 < m && visited[i][j + 1] != 1 && island[i][j + 1] >= island[i][j]){dfs(flag, i, j + 1, visited, island, n , m);}if(i - 1 >= 0 && visited[i - 1][j] != 1 && island[i - 1][j] >= island[i][j]){dfs(flag, i - 1, j, visited, island, n , m);}if(j - 1 >= 0 && visited[i][j - 1] != 1 && island[i][j - 1] >= island[i][j]){dfs(flag, i, j - 1, visited, island, n , m);}
}int main(){int n = 0, m = 0; cin >> n >> m;vector<vector<int>> visited1(n, vector<int>(m, 0));vector<vector<int>> visited2(n, vector<int>(m, 0));vector<vector<int>> island(n, vector<int>(m, 0));for(int i = 0; i < n; i++){for(int j = 0; j < m; j++){cin >> island[i][j];}}for(int i = 0; i < n; i++){dfs(0, i, 0, visited1, island, n, m);dfs(0, i, m - 1, visited2, island, n, m);}for(int j = 0; j < m; j++){dfs(0, 0, j, visited1, island, n, m);dfs(0, n - 1, j, visited2, island, n, m);}for(int i = 0; i < n; i++){for(int j = 0; j < m; j++){if(visited2[i][j] && visited1[i][j]){cout << i << " " << j << endl;}}}
}
104.建造最大岛屿
104. 建造最大岛屿 (kamacoder.com)
#include<iostream>
#include<vector>
#include<unordered_set>using namespace std;
const int dir[4][2] = {1, 0, 0, 1, -1, 0, 0, -1};
int counts = 0; // 用于记录岛屿面积
void dfs(int x, int y, vector<vector<int>> &island, vector<vector<int>> &visited, int mark){if(island[x][y] == 0 || visited[x][y]){return ;}island[x][y] = mark;counts++;visited[x][y] = 1;for(int i = 0; i < 4; i++){int nextX = x + dir[i][0], nextY = y + dir[i][1];if(nextX >= 0 && nextX < int(island.size()) && nextY >= 0 && nextY < int(island[0].size())){dfs(nextX, nextY, island, visited, mark);}}
}int main(){int n = 0, m = 0;cin >> n >> m;vector<vector<int>> island(n, vector<int>(m));vector<vector<int>> visited(n, vector<int>(m));for(int i = 0; i < n; i++){for(int j = 0; j < m; j++){cin >> island[i][j];}}int mark = 1, flag = 1;vector<int> markVec(m * n + 1);for(int i = 0; i < n; i++){for(int j = 0; j < m; j++){if(island[i][j] == 0){ // 全是岛屿flag = 0;}}}for(int i = 0; i < n; i++){for(int j = 0; j < m; j++){if(island[i][j] != 0 && visited[i][j] == 0){counts = 0;dfs(i, j, island, visited, mark);markVec[mark] = counts;mark++;}}}if(flag == 1){cout << m * n;return 0;}int ans = 0;unordered_set<int> markSet;for(int i = 0; i < n; i++){for(int j = 0; j < m; j++){if(island[i][j] == 0){for(int k = 0; k < 4; k++){int nextX = i + dir[k][0], nextY = j + dir[k][1];if(nextX >= 0 && nextX < int(island.size()) && nextY >= 0 && nextY < int(island[0].size())){markSet.insert(island[nextX][nextY]);}}int curArea = 0;for(auto index : markSet){curArea += markVec[index];}ans = max(ans, curArea);markSet.clear();}}}cout << ans + 1 << endl;return 0;
}