代码随想录训练营第五十二天 孤岛的总面积

第一题：孤岛的总面积

第二题：沉没孤岛

思路：

将所有在边界的岛屿所在的visited数组位置都置为true，剩下的visited[i][j] == true && grid[i][j] == 1的位置就是孤岛，将其置为1即可。

代码如下

#include <iostream>
#include <vector>
using namespace std;
int dir[4][2] = {-1, 0, 0, -1, 1, 0, 0, 1}; // 保存四个方向void dfs(vector<vector<int>>& grid, vector<vector<bool>>& visited, int x, int y) {visited[x][y] = true;for (int i = 0; i < 4; i++) { // 向四个方向遍历int nextx = x + dir[i][0];int nexty = y + dir[i][1];// 超过边界if (nextx < 0 || nextx >= grid.size() || nexty < 0 || nexty >= grid[0].size()) continue;// 不符合条件，不继续遍历if (grid[nextx][nexty] == 0) continue;if(!visited[nextx][nexty] && grid[nextx][nexty] == 1)dfs (grid, visited, nextx, nexty);}return;
}int main() {int n, m;cin >> n >> m;vector<vector<int>> grid(n, vector<int>(m, 0));for (int i = 0; i < n; i++) {for (int j = 0; j < m; j++) {cin >> grid[i][j];}}vector<vector<bool>> visited(n, vector<bool>(m, false));// 从左侧边，和右侧边 向中间遍历for (int i = 0; i < n; i++) {if (grid[i][0] == 1 && !visited[i][0]) dfs(grid, visited, i, 0);if (grid[i][m - 1] == 1 && !visited[i][m - 1]) dfs(grid, visited, i, m - 1);}// 从上边和下边 向中间遍历for (int j = 0; j < m; j++) {if (grid[0][j] == 1 && !visited[0][j]) dfs(grid, visited, 0, j);if (grid[n - 1][j] == 1 && !visited[n - 1][j]) dfs(grid, visited, n - 1, j);}for(int i = 0; i < n; i++){for(int j = 0; j < m; j++){if(!visited[i][j] && grid[i][j] == 1){grid[i][j] = 0;}}}for (int i = 0; i < n; i++) {for (int j = 0; j < m; j++) {cout << grid[i][j] << " " ;}cout << endl;}
}

第三题：水流问题

思路：

从第一组边界上的节点逆流而上，将遍历过的节点都标记上，

同样从第二组边界的边上节点逆流而上，将遍历过的节点也标记上

然后两方都标记过的节点就是目标节点

#include <iostream>
#include <vector>
using namespace std;
int n, m;
int dir[4][2] = {-1, 0, 0, -1, 1, 0, 0, 1};
void dfs(vector<vector<int>>& grid, vector<vector<bool>>& visited, int x, int y) {if (visited[x][y]) return;visited[x][y] = true;for (int i = 0; i < 4; i++) {int nextx = x + dir[i][0];int nexty = y + dir[i][1];if (nextx < 0 || nextx >= n || nexty < 0 || nexty >= m) continue;if (grid[x][y] > grid[nextx][nexty]) continue; // 注意：这里是从低向高遍历dfs (grid, visited, nextx, nexty);}return;
}int main() {cin >> n >> m;vector<vector<int>> grid(n, vector<int>(m, 0));for (int i = 0; i < n; i++) {for (int j = 0; j < m; j++) {cin >> grid[i][j];}}// 标记从第一组边界上的节点出发，可以遍历的节点vector<vector<bool>> firstBorder(n, vector<bool>(m, false));// 标记从第一组边界上的节点出发，可以遍历的节点vector<vector<bool>> secondBorder(n, vector<bool>(m, false));// 从最上和最下行的节点出发，向高处遍历for (int i = 0; i < n; i++) {dfs (grid, firstBorder, i, 0); // 遍历最左列，接触第一组边界dfs (grid, secondBorder, i, m - 1); // 遍历最右列，接触第二组边界}// 从最左和最右列的节点出发，向高处遍历for (int j = 0; j < m; j++) {dfs (grid, firstBorder, 0, j); // 遍历最上行，接触第一组边界dfs (grid, secondBorder, n - 1, j); // 遍历最下行，接触第二组边界}for (int i = 0; i < n; i++) {for (int j = 0; j < m; j++) {// 如果这个节点，从第一组边界和第二组边界出发都遍历过，就是结果if (firstBorder[i][j] && secondBorder[i][j]) cout << i << " " << j << endl;;}}}

第四题：建造最大工岛

思路：

第一步：先遍历一遍地图，得出各个岛屿的面积，并做编号记录。可以使用map记录，key为岛屿编号，value为岛屿面积

第二部：再遍历地图，遍历0的方格，并统计该1(由0变成1)周围岛屿面积，将其相邻面积相加在一起，遍历所有0之后，就可以得出选一个0变成1之后的最大面积。

代码如下：

#include <iostream>
#include <vector>
#include <unordered_set>
#include <unordered_map>
using namespace std;
int n, m;
int count;int dir[4][2] = {0, 1, 1, 0, -1, 0, 0, -1}; // 四个方向
void dfs(vector<vector<int>>& grid, vector<vector<bool>>& visited, int x, int y, int mark) {if (visited[x][y] || grid[x][y] == 0) return; // 终止条件：访问过的节点 或者 遇到海水visited[x][y] = true; // 标记访问过grid[x][y] = mark; // 给陆地标记新标签count++;for (int i = 0; i < 4; i++) {int nextx = x + dir[i][0];int nexty = y + dir[i][1];if (nextx < 0 || nextx >= n || nexty < 0 || nexty >= m) continue;  // 越界了，直接跳过dfs(grid, visited, nextx, nexty, mark);}
}int main() {cin >> n >> m;vector<vector<int>> grid(n, vector<int>(m, 0));for (int i = 0; i < n; i++) {for (int j = 0; j < m; j++) {cin >> grid[i][j];}}vector<vector<bool>> visited(n, vector<bool>(m, false)); // 标记访问过的点unordered_map<int ,int> gridNum;int mark = 2; // 记录每个岛屿的编号bool isAllGrid = true; // 标记是否整个地图都是陆地for (int i = 0; i < n; i++) {for (int j = 0; j < m; j++) {if (grid[i][j] == 0) isAllGrid = false;if (!visited[i][j] && grid[i][j] == 1) {count = 0;dfs(grid, visited, i, j, mark); // 将与其链接的陆地都标记上 truegridNum[mark] = count; // 记录每一个岛屿的面积mark++; // 记录下一个岛屿编号}}}if (isAllGrid) {cout << n * m << endl; // 如果都是陆地，返回全面积return 0; // 结束程序}// 以下逻辑是根据添加陆地的位置，计算周边岛屿面积之和int result = 0; // 记录最后结果unordered_set<int> visitedGrid; // 标记访问过的岛屿for (int i = 0; i < n; i++) {for (int j = 0; j < m; j++) {count = 1; // 记录连接之后的岛屿数量visitedGrid.clear(); // 每次使用时，清空if (grid[i][j] == 0) {for (int k = 0; k < 4; k++) {int neari = i + dir[k][1]; // 计算相邻坐标int nearj = j + dir[k][0];if (neari < 0 || neari >= n || nearj < 0 || nearj >= m) continue;if (visitedGrid.count(grid[neari][nearj])) continue; // 添加过的岛屿不要重复添加// 把相邻四面的岛屿数量加起来count += gridNum[grid[neari][nearj]];visitedGrid.insert(grid[neari][nearj]); // 标记该岛屿已经添加过}}result = max(result, count);}}cout << result << endl;}