代码随想录day52图论3

101. 孤岛的总面积

题目链接
文章讲解

#include<bits/stdc++.h>
using namespace std;int ans = 0;       // 记录不与边界相连的孤岛数量
int sum = 0;       // 当前孤岛的面积
bool flag = false; // 标记当前孤岛是否与边界相连
// 方向数组：右，下，左，上
int direct[4][2] = {0, 1, 1, 0, -1, 0, 0, -1};// 广度优先搜索（BFS）函数，用于遍历连通区域
void bfs(vector<vector<int>>& grid, vector<vector<bool>>& visit, int x, int y)
{queue<pair<int, int>> q;q.push({x, y});visit[x][y] = true;while(!q.empty()){pair<int, int> cur = q.front();q.pop();int curx = cur.first;int cury = cur.second;// 遍历四个方向for(int i = 0; i < 4; i++){int nextx = curx + direct[i][0];int nexty = cury + direct[i][1];// 如果下一个位置越界，跳过if(nextx < 0 || nextx >= grid.size() || nexty < 0 || nexty >= grid[0].size()) continue;// 如果该位置是陆地且未访问过if(grid[nextx][nexty] == 1 && !visit[nextx][nexty]){q.push({nextx, nexty});  // 将新的位置加入队列visit[nextx][nexty] = true;  // 标记该位置为已访问sum++;  // 当前孤岛的面积加一// 如果当前孤岛接触到边界，则设置标记为 trueif(nextx == 0 || nextx == grid.size() - 1 || nexty == 0 || nexty == grid[0].size() - 1)flag = true;}}}
}int main(){int n, m;cin >> n >> m;  // 输入网格的行数和列数// 初始化网格和访问标记数组vector<vector<int>> grid(n, vector<int>(m, 0));  // 网格，0表示水域，1表示陆地vector<vector<bool>> visit(n, vector<bool>(m, false));  // 访问标记数组，初始为未访问// 输入网格的数据for(int i = 0; i < n; i++){for(int j = 0; j < m; j++){cin >> grid[i][j];  // 输入每个位置的值}}// 遍历网格内部的区域（排除边界区域）for(int i = 1; i < n - 1; i++)  // 遍历行，从第2行到倒数第2行{for(int j = 1; j < m - 1; j++)  // 遍历列，从第2列到倒数第2列{// 如果当前位置是陆地且未访问过，启动 BFS 遍历该连通区域if(!visit[i][j] && grid[i][j] == 1){sum = 1;  // 当前孤岛的面积从1开始（包括当前位置）flag = false;  // 初始化标记，假设该孤岛不与边界相连bfs(grid, visit, i, j);  // 执行 BFS，遍历孤岛// 如果该孤岛没有接触到边界，则将其计入最终结果if(!flag) ans += sum;}}}// 输出最终结果：不与边界相连的孤岛总面积cout << ans;
}

102. 沉没孤岛

题目链接
文章讲解

#include<bits/stdc++.h>
using namespace std;bool flag;  // 标记当前岛屿是否与边界相连
int direct[4][2] = {0, 1, 1, 0, -1, 0, 0, -1};  // 方向数组：右、下、左、上// BFS 用于遍历并判断孤岛是否与边界相连
void bfs(vector<vector<int>>& grid, vector<vector<bool>>& visit, int x, int y)
{queue<pair<int, int>> q;q.push({x, y});visit[x][y] = true;// 如果岛屿接触到边界，标记为与边界相连if(x == 0 || x == grid.size() - 1 || y == 0 || y == grid[0].size() - 1)flag = true;// 开始 BFS 遍历while(!q.empty()){pair<int, int> cur = q.front();q.pop();int curx = cur.first;int cury = cur.second;// 遍历四个方向for(int i = 0; i < 4; i++){int nextx = curx + direct[i][0];int nexty = cury + direct[i][1];// 如果下一个位置越界，跳过if(nextx < 0 || nextx >= grid.size() || nexty < 0 || nexty >= grid[0].size()) continue;// 如果是陆地且未访问过if(grid[nextx][nexty] == 1 && !visit[nextx][nexty]){q.push({nextx, nexty});visit[nextx][nexty] = true;// 如果接触到边界，将 flag 设置为 trueif(nextx == 0 || nextx == grid.size() - 1 || nexty == 0 || nexty == grid[0].size() - 1)flag = true;}}}
}// BFS2 用于将不与边界相连的岛屿沉没
void bfs2(vector<vector<int>>& grid, vector<vector<bool>>& visit, int x, int y)
{queue<pair<int, int>> q;q.push({x, y});visit[x][y] = true;grid[x][y] = 0;  // 沉没该岛屿部分// 开始 BFS 沉没孤岛while(!q.empty()){pair<int, int> cur = q.front();q.pop();int curx = cur.first;int cury = cur.second;// 遍历四个方向for(int i = 0; i < 4; i++){int nextx = curx + direct[i][0];int nexty = cury + direct[i][1];// 如果下一个位置越界，跳过if(nextx < 0 || nextx >= grid.size() || nexty < 0 || nexty >= grid[0].size()) continue;// 如果是陆地且未访问if(grid[nextx][nexty] == 1){q.push({nextx, nexty});visit[nextx][nexty] = true;grid[nextx][nexty] = 0;  // 沉没该岛屿部分}}}
}int main(){int n, m;cin >> n >> m;  // 输入网格的行数和列数vector<vector<int>> grid(n, vector<int>(m, 0));  // 网格初始化，默认都是水域（0）vector<vector<bool>> visit(n, vector<bool>(m, false));  // 访问标记数组// 输入网格数据，1 表示陆地，0 表示水域for(int i = 0; i < n; i++){for(int j = 0; j < m; j++){cin >> grid[i][j];}}// 遍历网格中的所有陆地for(int i = 0; i < n; i++){for(int j = 0; j < m; j++){// 对每个未访问过的陆地执行 BFSif(!visit[i][j] && grid[i][j] == 1)  {flag = false;  // 假设当前孤岛不与边界相连bfs(grid, visit, i, j);  // 执行 BFS，检查该岛屿是否与边界相连if(!flag)  // 如果孤岛不与边界相连，则将其沉没{bfs2(grid, visit, i, j);}}}}// 输出沉没后的网格for(int i = 0; i < n; i++){for(int j = 0; j < m; j++){cout << grid[i][j];if(j == m - 1) cout << endl;  // 每行末尾换行else cout << " ";  // 每个元素间加空格}}return 0;
}

103. 水流问题

题目链接
文章讲解

#include<bits/stdc++.h>
using namespace std;// 方向数组：右，下，左，上
int direct[4][2] = {0, 1, 1, 0, -1, 0, 0, -1};// BFS 用于遍历网格，找到所有符合条件的点
void bfs(vector<vector<int>>& grid, vector<vector<bool>>& visit, int x, int y) {queue<pair<int, int>> q;q.push({x, y});visit[x][y] = true;while (!q.empty()) {auto cur = q.front();q.pop();int curx = cur.first;int cury = cur.second;// 遍历四个方向for (int i = 0; i < 4; i++) {int nextx = curx + direct[i][0];int nexty = cury + direct[i][1];// 边界检查if (nextx < 0 || nexty < 0 || nextx >= grid.size() || nexty >= grid[0].size())continue;// 如果满足条件且未访问过if (grid[nextx][nexty] >= grid[curx][cury] && !visit[nextx][nexty]) {q.push({nextx, nexty});visit[nextx][nexty] = true;}}}
}int main() {int n, m;cin >> n >> m;// 初始化 grid，二维矩阵，初值为 0vector<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>> lb(n, vector<bool>(m, false));vector<vector<bool>> rb(n, vector<bool>(m, false));// 从上边界和下边界出发进行 BFSfor (int i = 0; i < m; i++) {bfs(grid, lb, 0, i);    // 从上边界bfs(grid, rb, n - 1, i); // 从下边界}// 从左边界和右边界出发进行 BFSfor (int i = 0; i < n; i++) {bfs(grid, lb, i, 0);    // 从左边界bfs(grid, rb, i, m - 1); // 从右边界}// 输出可以同时从第一组和第二组边界流出的坐标for (int i = 0; i < n; i++) {for (int j = 0; j < m; j++) {if (lb[i][j] && rb[i][j]) {cout << i << " " << j << endl;}}}return 0;
}

104.建造最大岛屿

题目链接
文章讲解
先遍历所有的陆地块 1，用 BFS 把每个岛屿标记为不同的编号（从 2 开始），并记录每个岛屿的面积。

遍历所有的水块 0，尝试将其变成 1，并计算其上下左右 4 个方向连接的不同岛屿编号的面积和，得到变换后的最大面积。

特判：如果原始矩阵全是陆地，则直接返回 n * m。

#include <iostream>
#include <vector>
#include <unordered_map>
#include <unordered_set>
#include <queue>
using namespace std;int n, m;
int dir[4][2] = {0, 1, 1, 0, -1, 0, 0, -1}; // 右 下 左 上// BFS 标记岛屿 & 计算面积
int bfs(vector<vector<int>>& grid, vector<vector<bool>>& visited, int x, int y, int mark) {int area = 0;queue<pair<int, int>> q;q.push({x, y});visited[x][y] = true;grid[x][y] = mark;while (!q.empty()) {auto [cx, cy] = q.front(); q.pop();area++;for (int i = 0; i < 4; i++) {int nx = cx + dir[i][0];int ny = cy + dir[i][1];if (nx >= 0 && nx < n && ny >= 0 && ny < m &&!visited[nx][ny] && grid[nx][ny] == 1) {q.push({nx, ny});visited[nx][ny] = true;grid[nx][ny] = mark;}}}return area;
}int main() {cin >> n >> m;vector<vector<int>> grid(n, vector<int>(m));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> area_map; // mark -> areaint mark = 2; // 岛屿编号从2开始// Step 1: 标记岛屿编号并统计面积for (int i = 0; i < n; ++i) {for (int j = 0; j < m; ++j) {if (!visited[i][j] && grid[i][j] == 1) {int area = bfs(grid, visited, i, j, mark);area_map[mark] = area;mark++;}}}// Step 2: 尝试将每个水块变为陆地，记录最大面积int max_area = 0;bool all_land = true;for (int i = 0; i < n; ++i) {for (int j = 0; j < m; ++j) {if (grid[i][j] == 0) {all_land = false;unordered_set<int> seen; // 记录周围不同的岛屿int total = 1; // 当前水变陆地后的初始面积为1for (int d = 0; d < 4; ++d) {int ni = i + dir[d][0];int nj = j + dir[d][1];if (ni >= 0 && ni < n && nj >= 0 && nj < m) {int neighbor_mark = grid[ni][nj];if (neighbor_mark > 1 && !seen.count(neighbor_mark)) {total += area_map[neighbor_mark];seen.insert(neighbor_mark);}}}max_area = max(max_area, total);}}}// 如果全是陆地，没有任何水块if (all_land) {cout << n * m << endl;} else {cout << max_area << endl;}return 0;
}