代码随想录day52 101孤岛的总面积 102沉没孤岛 103水流问题 104建造最大岛屿

代码随想录

#include <iostream>
#include <vector>using namespace std;
int count = 0;
int dir[4][2] = {{1, 0}, {0, 1}, {-1 ,0}, {0, -1}};void dfs(vector<vector<int>> &graph, int row, int col) {graph[row][col] = 0;count++;for (int i = 0; i < 4; i++) {int nextRow = row + dir[i][0];int nextCol = col + dir[i][1];if (nextRow < 0 || nextRow >= graph.size() || nextCol < 0 || nextCol >= graph[0].size()) {continue;}if (graph[nextRow][nextCol] == 1) {dfs(graph, nextRow, nextCol);}}
}int main() {int N, M;cin >> N >> M;vector<vector<int>> graph(N, vector<int>(M));for (int i = 0; i < N; i++) {for (int j = 0; j < M; j++) {cin >> graph[i][j];}}for (int i = 0; i < N; i++) {if (graph[i][0] == 1) {dfs(graph, i, 0);}if (graph[i][M - 1] == 1) {dfs(graph, i, M - 1);}}for (int j = 0; j < M; j++) {if (graph[0][j] == 1) {dfs(graph, 0, j);}if (graph[N - 1][j] == 1) {dfs(graph, N - 1, j);}}count = 0;for (int i = 1; i < N - 1; i++) {for (int j = 1; j < M - 1; j++) {if (graph[i][j] == 1) {dfs(graph, i, j);}}}cout << count;return 0;
}

#include <iostream>
#include <vector>
#include <queue>using namespace std;int count = 0;
int dir[4][2] = {{1, 0}, {0, 1}, {-1 ,0}, {0, -1}};void bfs(vector<vector<int>> &graph, int row, int col) {count++;graph[row][col] = 0;queue<pair<int, int>> que;que.push({row, col});while (!que.empty()){pair<int, int> pa = que.front();que.pop();for (int i = 0; i < 4; i++) {int nextRow = pa.first + dir[i][0];int nextCol = pa.second + dir[i][1];if (nextRow < 0 || nextRow >= graph.size() || nextCol < 0 || nextCol >= graph[0].size()) {continue;}if (graph[nextRow][nextCol] == 1) {count++;graph[nextRow][nextCol] = 0;que.push({nextRow, nextCol});}}}
}int main() {int N, M;cin >> N >> M;vector<vector<int>> graph(N, vector<int>(M));for (int i = 0; i < N; i++) {for (int j = 0; j < M; j++) {cin >> graph[i][j];}}for (int i = 0; i < N; i++) {if (graph[i][0] == 1) {bfs(graph, i, 0);}if (graph[i][M - 1] == 1) {bfs(graph, i, M - 1);}}for (int j = 0; j < M; j++) {if (graph[0][j] == 1) {bfs(graph, 0, j);}if (graph[N - 1][j] == 1) {bfs(graph, N - 1, j);}}count = 0;for (int i = 1; i < N - 1; i++) {for (int j = 1; j < M - 1; j++) {if (graph[i][j] == 1) {bfs(graph, i, j);}}}cout << count;return 0;
}

代码随想录

#include <iostream>
#include <vector>using namespace std;int dir[4][2] = {{1, 0}, {0, 1}, {-1 ,0}, {0, -1}};void dfs(vector<vector<int>> &graph, int row, int col) {graph[row][col] = 2;for (int i = 0; i < 4; i++) {int nextRow = row + dir[i][0];int nextCol = col + dir[i][1];if (nextRow < 0 || nextRow >= graph.size() || nextCol < 0 || nextCol >= graph[0].size()) {continue;}if (graph[nextRow][nextCol] == 1) {dfs(graph, nextRow, nextCol);}}
}int main() {int N, M;cin >> N >> M;vector<vector<int>> graph(N, vector<int>(M));for (int i = 0; i < N; i++) {for (int j = 0; j < M; j++) {cin >> graph[i][j];}}for (int i = 0; i < N; i++) {if (graph[i][0] == 1) {dfs(graph, i, 0);}if (graph[i][M - 1] == 1) {dfs(graph, i, M - 1);}}for (int j = 0; j < M; j++) {if (graph[0][j] == 1) {dfs(graph, 0, j);}if (graph[N - 1][j] == 1) {dfs(graph, N - 1, j);}}for (int i = 0; i < N; i++) {for (int j = 0; j < M; j++) {if (graph[i][j] != 0) {graph[i][j]--;}cout << graph[i][j] << " ";}cout << "\n";}return 0;
}

#include <iostream>
#include <vector>
#include <queue>using namespace std;int dir[4][2] = {{1, 0}, {0, 1}, {-1 ,0}, {0, -1}};void bfs(vector<vector<int>> &graph, int row, int col) {graph[row][col] = 2;queue<pair<int, int>> que;que.push({row, col});while (!que.empty()) {int curRow = que.front().first;int curCol = que.front().second;que.pop();for (int i = 0; i < 4; i++) {int nextRow = curRow + dir[i][0];int nextCol = curCol + dir[i][1];if (nextRow < 0 || nextRow >= graph.size() || nextCol < 0 || nextCol >= graph[0].size()) {continue;}if (graph[nextRow][nextCol] == 1) {que.push({nextRow, nextCol});graph[nextRow][nextCol] = 2;}}}
}int main() {int N, M;cin >> N >> M;vector<vector<int>> graph(N, vector<int>(M));for (int i = 0; i < N; i++) {for (int j = 0; j < M; j++) {cin >> graph[i][j];}}for (int i = 0; i < N; i++) {if (graph[i][0] == 1) {bfs(graph, i, 0);}if (graph[i][M - 1] == 1) {bfs(graph, i, M - 1);}}for (int j = 0; j < M; j++) {if (graph[0][j] == 1) {bfs(graph, 0, j);}if (graph[N - 1][j] == 1) {bfs(graph, N - 1, j);}}for (int i = 0; i < N; i++) {for (int j = 0; j < M; j++) {if (graph[i][j] != 0) {graph[i][j]--;}cout << graph[i][j] << " ";}cout << "\n";}return 0;
}

代码随想录

#include <vector>
#include <iostream>using namespace std;int dir[4][2] = {{1, 0}, {0, 1}, {-1, 0}, {0, -1}};
void dfs(vector<vector<int>> &graph, vector<vector<bool>> &visted, int row, int col) {visted[row][col] = true;for (int i = 0; i < 4; i++) {int nextRow = row + dir[i][0];int nextCol = col + dir[i][1];if (nextRow < 0 || nextRow >= graph.size() || nextCol < 0 || nextCol >= graph[0].size()) {continue;}if (graph[nextRow][nextCol] >= graph[row][col] && !visted[nextRow][nextCol]) {dfs(graph, visted, nextRow, nextCol);}}
}int main() {int N, M;cin >> N >> M;vector<vector<int>> graph(N, vector<int>(M));for (int i = 0; i < N; i++) {for (int j = 0; j < M; j++) {cin >> graph[i][j];}}vector<vector<bool>> firstBoard(N, vector<bool>(M, false));vector<vector<bool>> secondBoard(N, vector<bool>(M, false));for (int i = 0; i < N; i++) {dfs(graph, firstBoard, i, 0);dfs(graph, secondBoard, i, M - 1);}for (int j = 0; j < M; j++) {dfs(graph, firstBoard, 0, j);dfs(graph, secondBoard, N - 1, j);}for (int i = 0; i < N; i++) {for (int j = 0; j < M; j++) {if (firstBoard[i][j] && secondBoard[i][j]) {cout << i << " " << j << "\n";}}}return 0;
}

代码随想录

#include <iostream>
#include <vector>
#include <unordered_map>
#include <unordered_set>using namespace std;int dir[4][2] = {{1, 0}, {0, 1}, {-1, 0}, {0, -1}};
int count;
void dfs(vector<vector<int>> &graph, vector<vector<bool>> &visted, int row, int col, int mark) {count++;visted[row][col] = true;graph[row][col] = mark;for (int i = 0; i < 4; i++) {int nextRow = row + dir[i][0];int nextCol = col + dir[i][1];if (nextRow < 0 || nextRow >= graph.size() || nextCol < 0 || nextCol >= graph[0].size()) {continue;}if (graph[nextRow][nextCol] == 1 && !visted[nextRow][nextCol]) {dfs(graph, visted, nextRow, nextCol, mark);}}
}int main() {int N, M;cin >> N >> M;vector<vector<int>> graph(N, vector<int>(M));for (int i = 0; i < N; i++) {for (int j = 0; j < M; j++) {cin >> graph[i][j];}}bool isAllLand = true;vector<vector<bool>> visted(N, vector<bool>(M, false));unordered_map<int, int> umap;int mark = 2;for (int i = 0; i < N; i++) {for (int j = 0; j < M; j++) {if (graph[i][j] == 0) {isAllLand = false;}if (graph[i][j] == 1 && !visted[i][j]) {count = 0;dfs(graph, visted, i, j, mark);umap[mark] = count;mark++;}}}if (isAllLand) {cout << M * N;return 0;}int result = 0;unordered_set<int> vistedLand;for (int i = 0; i < N; i++) {for (int j = 0; j < M; j++) {if (graph[i][j] == 0) {count = 1;vistedLand.clear();for (int k = 0; k < 4; k++) {int nextRow = i + dir[k][0];int nextCol = j + dir[k][1];if (nextRow < 0 || nextRow >= graph.size() || nextCol < 0 || nextCol >= graph[0].size()) {continue;}mark = graph[nextRow][nextCol];if (vistedLand.count(mark) != 0 || mark < 2) {continue;}count += umap[mark];vistedLand.insert(mark);}result = max(result, count);}}}cout << result;return 0;
}