当前位置：首页 > news >正文

Day52_图论3.md

news 2026/3/26 20:44:25

Day52_图论3.md

孤岛的总面积

题目描述

在由0和1组成的二维数组中，寻找上下左右四个方向都被0包裹的1的总数。
输入：
第1行输入二维数组的行数和列数；
此后输入n*m；

思路：

这道题目一开始想的是先找到岛，其次判断是不是边界上的岛，最后统计孤岛的面积。
如此势必要写岛的四边的判断条件。
题解的思路是：首先排除边上所有的岛，然后对剩余的陆地进行计数。

遇到的问题：

在dfs函数中，首先进行海水化的操作，其次进行边界判断，最后判断是不是陆地。即先进行数组越界判断，然后进行元素判断，不能改变顺序，否则会产生段错误；
在靠边的陆地判断中，坐标容易搞错。

实现

# include<iostream>
# include<vector>
using namespace std;
void dfs(vector<vector<int>> &grid,int x,int y){grid[x][y]=0;int dir[4][2]={0,1,0,-1,1,0,-1,0};for(int i=0;i<4;i++){int nextx=x+dir[i][1];int nexty=y+dir[i][0];if(nextx<0||nextx>=grid.size()||nexty<0||nexty>=grid[0].size()){continue;}if(grid[nextx][nexty]==0){continue; }dfs(grid,nextx,nexty);}
}
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];}}for(int i=0;i<n;i++){if(grid[i][0]==1)dfs(grid,i,0);if(grid[i][m-1]==1)dfs(grid,i,m-1);}for(int j=0;j<m;j++){if(grid[0][j]==1)dfs(grid,0,j);if(grid[n-1][j]==1)dfs(grid,n-1,j);}int count=0;for(int i=0;i<n;i++){for(int j=0;j<m;j++){if(grid[i][j]==1){count++;}}}cout<<count<<endl;return 0;
}

沉默孤岛

问题描述

将位于中央的所有孤岛变为海水，输出处理后的矩阵。上一道题目是把周围的陆地变成海水，这次是把中间的岛变成海水。

实现

# include<iostream>
# include<vector>
using namespace std;
void dfs(vector<vector<int>> &grid,int x,int y){grid[x][y]=2;int dir[4][2]={0,1,0,-1,1,0,-1,0};for(int i=0;i<4;i++){int nextx=x+dir[i][1];int nexty=y+dir[i][0];if(nextx<0||nextx>=grid.size()||nexty<0||nexty>=grid[0].size()){continue;}if(grid[nextx][nexty]==0||grid[nextx][nexty]==2){continue; }dfs(grid,nextx,nexty);}
}
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];}}for(int i=0;i<n;i++){if(grid[i][0]==1)dfs(grid,i,0);if(grid[i][m-1]==1)dfs(grid,i,m-1);}for(int j=0;j<m;j++){if(grid[0][j]==1)dfs(grid,0,j);if(grid[n-1][j]==1)dfs(grid,n-1,j);}for(int i=0;i<n;i++){for(int j=0;j<m;j++){if(grid[i][j]==1){grid[i][j]=0;}if(grid[i][j]==2){grid[i][j]=1;}}}for(int i=0;i<n;i++){for(int j=0;j<m;j++){cout<<grid[i][j]<<" ";}cout<<endl;
}
}

水流问题

问题描述

给定一个矩阵，输出一些元素的坐标，该坐标满足从某一方向上不递增地大于边界元素值。
如果这个矩阵只有两行或者两列，那么其所有元素都是边界元素，那还需要输出吗？

思路：

先确定外围的，然后向里逼近。
一个元素，只要比它上下左右四个方向上任意一个方向的值大，就可以输出其坐标。

题目理解有误。图中（3，3）的值是不满足条件的。

#include <iostream>
#include <vector>
using namespace std;
int n, m;
int dir[4][2] = {-1, 0, 0, -1, 1, 0, 0, 1};// 从 x，y 出发 把可以走的地方都标记上
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>> FirstBound(n, vector<bool>(m, false));vector<vector<bool>> SecondBound(n, vector<bool>(m, false));for(int i=0;i<n;i++){dfs(grid,FirstBound,i,0);dfs(grid,SecondBound,i,m-1);}//左右//vector<vector<bool>> visited(n, vector<bool>(m, false));for(int j=0;j<m;j++){dfs(grid,FirstBound,0,j);dfs(grid,SecondBound,n-1,j);}// 遍历每一个点，看是否能同时到达第一组边界和第二组边界for (int i = 0; i < n; i++) {for (int j = 0; j < m; j++) {if (FirstBound[i][j]&&SecondBound[i][j]) {cout << i << " " << j << endl;}}}