孤岛的总面积
题目描述
在由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;}}}
最大岛屿
把任何一块水域变成陆地，使得生成的岛屿有最大的面积。
思路
1.对岛屿进行标记； 通过dfs找到岛并记录岛屿的大小，通过一个unordered_map实现岛屿编号和岛屿大小的映射关系。
2.遍历每一格海水，记录最大岛屿面积；如果该格是海水，就把上下左右四面的岛屿总数相加；
为什么需要一个visitedGrid把走过的标记一遍呢？