KamaCoder101.孤岛的总面积
101. 孤岛的总面积
1.思路
DFS
方式一
使用独立的used矩阵和全局变量flag,cnt。dfs 函数探索、计数、判断是否触及边界。逐个探索岛屿，判断其是否封闭，累加面积。
#include <iostream> #include <vector> using namespace std; int flag,cnt; int dir[4][2]={0,-1,-1,0,0,1,1,0}; void dfs(vector<vector<int>>&graph,vector<vector<bool>>&used,int x,int y){ if(graph[x][y]==0 || used[x][y]) return; if(x==1 || x==graph.size()-1 || y==1 || y==graph[0].size()-1) flag=1; used[x][y]=true; cnt++; for(int i=0;i<4;i++){ int nextx=x+dir[i][0]; int nexty=y+dir[i][1]; if(nextx<1 || nextx>=graph.size() || nexty<1 || nexty>=graph[0].size()) continue; dfs(graph,used,nextx,nexty); } } int main(){ int n,m;cin>>n>>m; vector<vector<int>>graph(n+1,vector<int>(m+1,0)); for(int i=1;i<=n;i++){ for(int j=1;j<=m;j++){ cin>>graph[i][j]; } } vector<vector<bool>>used(n+1,vector<bool>(m+1,0)); int res=0; for(int i=1;i<=n;i++){ for(int j=1;j<=m;j++){ if(graph[i][j]==1 && !used[i][j]){ flag=0; cnt=0; dfs(graph,used,i,j); if(flag==0){ res+=cnt; } } } } cout<<res; return 0; }方式二
直接修改输入的graph矩阵，原地标记。dfs 函数清除与边界相连的陆地。先清除所有开放岛屿，再统计剩余的封闭岛屿面积。
#include <iostream> #include <vector> using namespace std; int dir[4][2]={0,-1,-1,0,0,1,1,0}; void dfs(vector<vector<int>>&graph,int x,int y){ graph[x][y]=0; for(int i=0;i<4;i++){ int nextx=x+dir[i][0]; int nexty=y+dir[i][1]; if(nextx<1 || nextx>=graph.size() || nexty<1 || nexty>=graph[0].size()) continue; if(graph[nextx][nexty]==0) continue; // 不符合条件，不继续遍历 dfs(graph,nextx,nexty); } } int main(){ int n,m;cin>>n>>m; vector<vector<int>>graph(n+1,vector<int>(m+1,0)); for(int i=1;i<=n;i++){ for(int j=1;j<=m;j++){ cin>>graph[i][j]; } } // 从左侧边，和右侧边 向中间遍历 for(int i=1;i<=n;i++){ if(graph[i][1]==1) dfs(graph,i,0); if(graph[i][m]==1) dfs(graph,i,m); } // 从上边和下边 向中间遍历 for(int j=1;j<=m;j++){ if(graph[1][j]==1) dfs(graph,1,j); if(graph[n][j]==1) dfs(graph,n,j); } int res=0; for(int i=1;i<=n;i++){ for(int j=1;j<=m;j++){ if(graph[i][j]==1) res++; } } cout<<res; return 0; }BFS
#include <iostream> #include <vector> #include <queue> using namespace std; int dir[4][2]={0,-1,-1,0,0,1,1,0}; void bfs(vector<vector<int>>&graph,int x,int y){ queue<pair<int,int>>que; que.push({x,y}); graph[x][y]=0; // 只要加入队列立刻标记 while(!que.empty()){ pair<int,int> cur=que.front();que.pop(); for(int i=0;i<4;i++){ int nextx=cur.first+dir[i][0]; int nexty=cur.second+dir[i][1]; if(nextx<1 || nextx>=graph.size() || nexty<1 || nexty>=graph[0].size()) continue; if(graph[nextx][nexty]==1){ que.push({nextx,nexty}); graph[nextx][nexty]=0; // 只要加入队列立刻标记 } } } } int main(){ int n,m;cin>>n>>m; vector<vector<int>>graph(n+1,vector<int>(m+1,0)); for(int i=1;i<=n;i++){ for(int j=1;j<=m;j++){ cin>>graph[i][j]; } } // 从左侧边，和右侧边 向中间遍历 for(int i=1;i<=n;i++){ if(graph[i][1]==1) bfs(graph,i,0); if(graph[i][m]==1) bfs(graph,i,m); } // 从上边和下边 向中间遍历 for(int j=1;j<=m;j++){ if(graph[1][j]==1) bfs(graph,1,j); if(graph[n][j]==1) bfs(graph,n,j); } int res=0; for(int i=1;i<=n;i++){ for(int j=1;j<=m;j++){ if(graph[i][j]==1) res++; } } cout<<res; return 0; }2.思考
本题可以在原来 孤岛计数 的基础上增加全局变量 cnt 和 flag，只要当前孤岛有一个节点位于边界上，该座孤岛整体就被标记上 flag=1，然后只对 flag=0 的孤岛面积相加即可得到孤岛的总面积；也可以先从左侧边和右侧边，还有上侧边和下侧边清除与边界相连的岛屿，对剩下的岛计数即可。
3.Reference：101. 孤岛的总面积 | 代码随想录
KamaCoder102.沉没孤岛
102. 沉没孤岛
1.思路
步骤一：深搜或者广搜将地图周边的 1 （陆地）全部改成 2 （特殊标记）
步骤二：将水域中间 1 （陆地）全部改成 水域（0）
步骤三：将之前标记的 2 改为 1 （陆地）
#include <iostream> #include <vector> using namespace std; int dir[4][2]={0,-1,-1,0,0,1,1,0}; void dfs(vector<vector<int>>&graph,int x,int y){ graph[x][y]=2; for(int i=0;i<4;i++){ int nextx=x+dir[i][0]; int nexty=y+dir[i][1]; if(nextx<1 || nextx>=graph.size() || nexty<1 || nexty>=graph[0].size()) continue; if(graph[nextx][nexty]==0 || graph[nextx][nexty]==2) continue; // 不符合条件，不继续遍历 dfs(graph,nextx,nexty); } } int main(){ int n,m;cin>>n>>m; vector<vector<int>>graph(n+1,vector<int>(m+1,0)); for(int i=1;i<=n;i++){ for(int j=1;j<=m;j++){ cin>>graph[i][j]; } } for(int i=1;i<=n;i++){ if(graph[i][1]==1) dfs(graph,i,1); if(graph[i][m]==1) dfs(graph,i,m); } for(int j=1;j<=m;j++){ if(graph[1][j]==1) dfs(graph,1,j); if(graph[n][j]==1) dfs(graph,n,j); } for(int i=1;i<=n;i++){ for(int j=1;j<=m;j++){ if(graph[i][j]==2) cout<<1<<" "; else if(graph[i][j]==1) cout<<0<<" "; else cout<<graph[i][j]<<" "; } cout<<endl; } return 0; }2.思考
在上述题目的基础上只需要把相邻边界的岛屿标记为 2，然后剩下的 1 即为孤岛，然后在输出的时候，如果当前 graph[i][j] == 0，则输出 0；如果 graph[i][j] == 1，则输出 0，代表要沉没的孤岛；如果 graph[i][j] == 2，则输出 1，代表预处理的岛屿。
3.Reference：102. 沉没孤岛
KamaCoder103.高山流水
103. 高山流水
1.思路
我们可以反过来想，从第一组边界上的节点逆流而上，将遍历过的节点都标记 true。
同样从第二组边界的边上节点 逆流而上，将遍历过的节点也标记 true。
然后两方都标记过的节点就是既可以流向第一组边界也可以流向第二组边界的节点，也就是我们最后要求的节点。
DFS
#include <iostream> #include <vector> #include <queue> using namespace std; int dir[4][2]={0,-1,-1,0,0,1,1,0}; void dfs(vector<vector<int>>&graph,vector<vector<bool>>&border,int x,int y){ if(border[x][y]) return; border[x][y]=true; for(int i=0;i<4;i++){ int nextx=x+dir[i][0]; int nexty=y+dir[i][1]; if(nextx<1 || nextx>=graph.size() || nexty<1 || nexty>=graph[0].size()) continue; if(graph[nextx][nexty]>=graph[x][y]){ // 注意：这里是从低向高遍历 dfs(graph,border,nextx,nexty); } } } int main(){ int n,m;cin>>n>>m; vector<vector<int>>graph(n+1,vector<int>(m+1,0)); for(int i=1;i<=n;i++){ for(int j=1;j<=m;j++){ cin>>graph[i][j]; } } // 标记从第一组边界上的节点出发，可以遍历的节点 vector<vector<bool>>firstborder(n+1,vector<bool>(m+1,false)); // 标记从第一组边界上的节点出发，可以遍历的节点 vector<vector<bool>>secondborder(n+1,vector<bool>(m+1,false)); // 从最上和最下行的节点出发，向高处遍历 for(int i=1;i<=n;i++){ dfs(graph,firstborder,i,1); dfs(graph,secondborder,i,m); } // 从最左和最右列的节点出发，向高处遍历 for(int j=1;j<=m;j++){ dfs(graph,firstborder,1,j); dfs(graph,secondborder,n,j); } for(int i=1;i<=n;i++){ for(int j=1;j<=m;j++){ // 如果这个节点，从第一组边界和第二组边界出发都遍历过，就是结果 if(firstborder[i][j] && secondborder[i][j]){ cout<<i-1<<" "<<j-1<<endl; } } } return 0; }BFS
#include <iostream> #include <vector> #include <queue> using namespace std; int dir[4][2]={0,-1,-1,0,0,1,1,0}; void bfs(vector<vector<int>>&graph,vector<vector<bool>>&border,int x,int y){ queue<pair<int,int>>que; que.push({x,y}); border[x][y]=true; while(!que.empty()){ pair<int,int> cur=que.front();que.pop(); for(int i=0;i<4;i++){ int nextx=cur.first+dir[i][0]; int nexty=cur.second+dir[i][1]; if(nextx<1 || nextx>=graph.size() || nexty<1 || nexty>=graph[0].size()) continue; if(graph[cur.first][cur.second] <= graph[nextx][nexty] && !border[nextx][nexty]){ que.push({nextx,nexty}); border[nextx][nexty]=true; } } } } int main(){ int n,m;cin>>n>>m; vector<vector<int>>graph(n+1,vector<int>(m+1,0)); for(int i=1;i<=n;i++){ for(int j=1;j<=m;j++){ cin>>graph[i][j]; } } vector<vector<bool>>firstborder(n+1,vector<bool>(m+1,false)); vector<vector<bool>>secondborder(n+1,vector<bool>(m+1,false)); for(int i=1;i<=n;i++){ bfs(graph,firstborder,i,1); bfs(graph,secondborder,i,m); } for(int j=1;j<=m;j++){ bfs(graph,firstborder,1,j); bfs(graph,secondborder,n,j); } for(int i=1;i<=n;i++){ for(int j=1;j<=m;j++){ if(firstborder[i][j] && secondborder[i][j]){ cout<<i-1<<" "<<j-1<<endl; } } } return 0; }2.复杂度分析
时间复杂度：O(n*m) - DFS
本题看起来 时间复杂度好像是 ： n * (n * m) + m * (n * m) = (m * n) * (m + n) 。
其实看 dfs 函数的实现，有 border 数组记录走过的节点，而走过的节点是不会再走第二次的。
所以调用dfs函数，只要参数传入的是数组 firstborder，那么地图中每一个节点其实就遍历一次，无论你调用多少次。同理，调用dfs函数，只要参数传入的是数组 secondborder，地图中每个节点也只会遍历一次。
所以，这段代码的时间复杂度是 2 * n * m。 地图用每个节点就遍历了两次，参数传入 firstBorder 的时候遍历一次，参数传入 secondBorder 的时候遍历一次。
空间复杂度：O(n*m)
3.思考
这道题和上面那道题都是逆向思考的，本题要求某点的水可以流向第一组边界和第二组边界，如果直接正向求得话，需要遍历每一个节点，并且对每一个节点进行 DFS 或 BFS ，这样时间复杂度将会来到惊人得 O(n*m*n*m)。为了降低时间复杂度，我们想到了使用逆向的思维，分别从第一组的边和第二组的边去进行搜索，只要下一节点的高度大于当前节点，就进一步搜索，对于搜索到的点赋值为 true，代表从该组边出发可以到达该点，最后遍历每个节点，如果两个数组均为 true，则说明是我们要求的点。
4.Reference：103. 高山流水
KamaCoder104.建造最大岛屿
104. 建造最大岛屿
1.思路
第一步：一次遍历地图，得出各个岛屿的面积，并做编号记录。可以使用 map 记录，key 为岛屿编号，value 为岛屿面积
第二步：再遍历地图，遍历0的方格（因为要将0变成1），并统计该1（由0变成的1）周边岛屿面积，将其相邻面积相加在一起，遍历所有 0 之后，就可以得出 选一个0变成1 之后的最大面积。
#include <iostream> #include <vector> #include <unordered_map> #include <unordered_set> using namespace std; int cnt; int dir[4][2]={0,-1,-1,0,0,1,1,0}; void dfs(vector<vector<int>>&graph,vector<vector<int>>&used,int x,int y,int mark){ if(graph[x][y]==0 || used[x][y]) return; graph[x][y]=mark; 给陆地标记新标签 used[x][y]=true; cnt++; for(int i=0;i<4;i++){ int nextx=x+dir[i][0]; int nexty=y+dir[i][1]; if(nextx<1 || nextx>=graph.size() || nexty<1 || nexty>=graph[0].size()) continue; dfs(graph,used,nextx,nexty,mark); } } int main(){ int n,m;cin>>n>>m; vector<vector<int>>graph(n+1,vector<int>(m+1,0)); vector<vector<int>>used(n+1,vector<int>(m+1,0)); unordered_map<int,int>mp; for(int i=1;i<=n;i++){ for(int j=1;j<=m;j++){ cin>>graph[i][j]; } } int mark=2,res=0; // 记录每个岛屿的编号 for(int i=1;i<=n;i++){ for(int j=1;j<=m;j++){ if(graph[i][j]==1 && !used[i][j]){ cnt=0; dfs(graph,used,i,j,mark); // 将与其链接的陆地都标记上 true mp[graph[i][j]]=cnt; // 记录每一个岛屿的面积 res=max(res,cnt); // 让 res 保持最大岛屿面积的值，避免全是陆地的情况 mark++; // 记录下一个岛屿编号 } } } // 根据添加陆地的位置，计算周边岛屿面积之和 unordered_set<int>st; // 标记访问过的岛屿 for(int i=1;i<=n;i++){ for(int j=1;j<=m;j++){ if(graph[i][j]==0){ int scnt=1; // 假设将当前海变成陆地，初始化为1，记录连接之后的岛屿数量 st.clear(); for(int k=0;k<4;k++){ int neari=i+dir[k][0]; int nearj=j+dir[k][1]; if(neari<1 || neari>n || nearj<1 || nearj>m) continue; if(st.find(graph[neari][nearj]) != st.end()) continue; scnt+=mp[graph[neari][nearj]]; // 把相邻四面的岛屿数量加起来 st.insert(graph[neari][nearj]); // 标记该岛屿已经添加过 } res=max(res,scnt); } } } cout<<res; return 0; }2.思考
这道题非常得巧妙，先是把各个岛屿分块，然后给出编号，并在 map 中存入每个编号岛屿块的数量，然后依次遍历每个 graph[i][j] == 0 的节点，假设依次将它们变成陆地，然后寻找上下左右是否遇见有编号的岛屿块，如果有就计数，并用 set 去重，防止重复计数相同编号的岛屿，最后取每种情况下的最大值即可。
