淘宝客网站备案号免费模板简历下载

淘宝客网站备案号,免费模板简历下载,网络营销ppt模板,ppt模板下载素材网站KamaCoder101.孤岛的总面积 101. 孤岛的总面积 1.思路 DFS 方式一 使用独立的 used 矩阵和全局变量 flag, cnt。dfs 函数探索、计数、判断是否触及边界。逐个探索岛屿#xff0c;判断其是否封闭#xff0c;累加面积。 #include iostream #include vector…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(vectorvectorintgraph,vectorvectorboolused,int x,int y){ if(graph[x][y]0 || used[x][y]) return; if(x1 || xgraph.size()-1 || y1 || ygraph[0].size()-1) flag1; used[x][y]true; cnt; for(int i0;i4;i){ int nextxxdir[i][0]; int nextyydir[i][1]; if(nextx1 || nextxgraph.size() || nexty1 || nextygraph[0].size()) continue; dfs(graph,used,nextx,nexty); } } int main(){ int n,m;cinnm; vectorvectorintgraph(n1,vectorint(m1,0)); for(int i1;in;i){ for(int j1;jm;j){ cingraph[i][j]; } } vectorvectorboolused(n1,vectorbool(m1,0)); int res0; for(int i1;in;i){ for(int j1;jm;j){ if(graph[i][j]1 !used[i][j]){ flag0; cnt0; dfs(graph,used,i,j); if(flag0){ rescnt; } } } } coutres; 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(vectorvectorintgraph,int x,int y){ graph[x][y]0; for(int i0;i4;i){ int nextxxdir[i][0]; int nextyydir[i][1]; if(nextx1 || nextxgraph.size() || nexty1 || nextygraph[0].size()) continue; if(graph[nextx][nexty]0) continue; // 不符合条件不继续遍历 dfs(graph,nextx,nexty); } } int main(){ int n,m;cinnm; vectorvectorintgraph(n1,vectorint(m1,0)); for(int i1;in;i){ for(int j1;jm;j){ cingraph[i][j]; } } // 从左侧边和右侧边 向中间遍历 for(int i1;in;i){ if(graph[i][1]1) dfs(graph,i,0); if(graph[i][m]1) dfs(graph,i,m); } // 从上边和下边 向中间遍历 for(int j1;jm;j){ if(graph[1][j]1) dfs(graph,1,j); if(graph[n][j]1) dfs(graph,n,j); } int res0; for(int i1;in;i){ for(int j1;jm;j){ if(graph[i][j]1) res; } } coutres; 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(vectorvectorintgraph,int x,int y){ queuepairint,intque; que.push({x,y}); graph[x][y]0; // 只要加入队列立刻标记 while(!que.empty()){ pairint,int curque.front();que.pop(); for(int i0;i4;i){ int nextxcur.firstdir[i][0]; int nextycur.seconddir[i][1]; if(nextx1 || nextxgraph.size() || nexty1 || nextygraph[0].size()) continue; if(graph[nextx][nexty]1){ que.push({nextx,nexty}); graph[nextx][nexty]0; // 只要加入队列立刻标记 } } } } int main(){ int n,m;cinnm; vectorvectorintgraph(n1,vectorint(m1,0)); for(int i1;in;i){ for(int j1;jm;j){ cingraph[i][j]; } } // 从左侧边和右侧边 向中间遍历 for(int i1;in;i){ if(graph[i][1]1) bfs(graph,i,0); if(graph[i][m]1) bfs(graph,i,m); } // 从上边和下边 向中间遍历 for(int j1;jm;j){ if(graph[1][j]1) bfs(graph,1,j); if(graph[n][j]1) bfs(graph,n,j); } int res0; for(int i1;in;i){ for(int j1;jm;j){ if(graph[i][j]1) res; } } coutres; return 0; }2.思考本题可以在原来 孤岛计数 的基础上增加全局变量 cnt 和 flag只要当前孤岛有一个节点位于边界上该座孤岛整体就被标记上 flag1然后只对 flag0 的孤岛面积相加即可得到孤岛的总面积也可以先从左侧边和右侧边还有上侧边和下侧边清除与边界相连的岛屿对剩下的岛计数即可。3.Reference101. 孤岛的总面积 | 代码随想录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(vectorvectorintgraph,int x,int y){ graph[x][y]2; for(int i0;i4;i){ int nextxxdir[i][0]; int nextyydir[i][1]; if(nextx1 || nextxgraph.size() || nexty1 || nextygraph[0].size()) continue; if(graph[nextx][nexty]0 || graph[nextx][nexty]2) continue; // 不符合条件不继续遍历 dfs(graph,nextx,nexty); } } int main(){ int n,m;cinnm; vectorvectorintgraph(n1,vectorint(m1,0)); for(int i1;in;i){ for(int j1;jm;j){ cingraph[i][j]; } } for(int i1;in;i){ if(graph[i][1]1) dfs(graph,i,1); if(graph[i][m]1) dfs(graph,i,m); } for(int j1;jm;j){ if(graph[1][j]1) dfs(graph,1,j); if(graph[n][j]1) dfs(graph,n,j); } for(int i1;in;i){ for(int j1;jm;j){ if(graph[i][j]2) cout1 ; else if(graph[i][j]1) cout0 ; else coutgraph[i][j] ; } coutendl; } return 0; }2.思考在上述题目的基础上只需要把相邻边界的岛屿标记为 2然后剩下的 1 即为孤岛然后在输出的时候如果当前 graph[i][j] 0则输出 0如果 graph[i][j] 1则输出 0代表要沉没的孤岛如果 graph[i][j] 2则输出 1代表预处理的岛屿。3.Reference102. 沉没孤岛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(vectorvectorintgraph,vectorvectorboolborder,int x,int y){ if(border[x][y]) return; border[x][y]true; for(int i0;i4;i){ int nextxxdir[i][0]; int nextyydir[i][1]; if(nextx1 || nextxgraph.size() || nexty1 || nextygraph[0].size()) continue; if(graph[nextx][nexty]graph[x][y]){ // 注意这里是从低向高遍历 dfs(graph,border,nextx,nexty); } } } int main(){ int n,m;cinnm; vectorvectorintgraph(n1,vectorint(m1,0)); for(int i1;in;i){ for(int j1;jm;j){ cingraph[i][j]; } } // 标记从第一组边界上的节点出发可以遍历的节点 vectorvectorboolfirstborder(n1,vectorbool(m1,false)); // 标记从第一组边界上的节点出发可以遍历的节点 vectorvectorboolsecondborder(n1,vectorbool(m1,false)); // 从最上和最下行的节点出发向高处遍历 for(int i1;in;i){ dfs(graph,firstborder,i,1); dfs(graph,secondborder,i,m); } // 从最左和最右列的节点出发向高处遍历 for(int j1;jm;j){ dfs(graph,firstborder,1,j); dfs(graph,secondborder,n,j); } for(int i1;in;i){ for(int j1;jm;j){ // 如果这个节点从第一组边界和第二组边界出发都遍历过就是结果 if(firstborder[i][j] secondborder[i][j]){ couti-1 j-1endl; } } } 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(vectorvectorintgraph,vectorvectorboolborder,int x,int y){ queuepairint,intque; que.push({x,y}); border[x][y]true; while(!que.empty()){ pairint,int curque.front();que.pop(); for(int i0;i4;i){ int nextxcur.firstdir[i][0]; int nextycur.seconddir[i][1]; if(nextx1 || nextxgraph.size() || nexty1 || nextygraph[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;cinnm; vectorvectorintgraph(n1,vectorint(m1,0)); for(int i1;in;i){ for(int j1;jm;j){ cingraph[i][j]; } } vectorvectorboolfirstborder(n1,vectorbool(m1,false)); vectorvectorboolsecondborder(n1,vectorbool(m1,false)); for(int i1;in;i){ bfs(graph,firstborder,i,1); bfs(graph,secondborder,i,m); } for(int j1;jm;j){ bfs(graph,firstborder,1,j); bfs(graph,secondborder,n,j); } for(int i1;in;i){ for(int j1;jm;j){ if(firstborder[i][j] secondborder[i][j]){ couti-1 j-1endl; } } } 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.Reference103. 高山流水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(vectorvectorintgraph,vectorvectorintused,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 i0;i4;i){ int nextxxdir[i][0]; int nextyydir[i][1]; if(nextx1 || nextxgraph.size() || nexty1 || nextygraph[0].size()) continue; dfs(graph,used,nextx,nexty,mark); } } int main(){ int n,m;cinnm; vectorvectorintgraph(n1,vectorint(m1,0)); vectorvectorintused(n1,vectorint(m1,0)); unordered_mapint,intmp; for(int i1;in;i){ for(int j1;jm;j){ cingraph[i][j]; } } int mark2,res0; // 记录每个岛屿的编号 for(int i1;in;i){ for(int j1;jm;j){ if(graph[i][j]1 !used[i][j]){ cnt0; dfs(graph,used,i,j,mark); // 将与其链接的陆地都标记上 true mp[graph[i][j]]cnt; // 记录每一个岛屿的面积 resmax(res,cnt); // 让 res 保持最大岛屿面积的值避免全是陆地的情况 mark; // 记录下一个岛屿编号 } } } // 根据添加陆地的位置计算周边岛屿面积之和 unordered_setintst; // 标记访问过的岛屿 for(int i1;in;i){ for(int j1;jm;j){ if(graph[i][j]0){ int scnt1; // 假设将当前海变成陆地初始化为1记录连接之后的岛屿数量 st.clear(); for(int k0;k4;k){ int neariidir[k][0]; int nearjjdir[k][1]; if(neari1 || nearin || nearj1 || nearjm) continue; if(st.find(graph[neari][nearj]) ! st.end()) continue; scntmp[graph[neari][nearj]]; // 把相邻四面的岛屿数量加起来 st.insert(graph[neari][nearj]); // 标记该岛屿已经添加过 } resmax(res,scnt); } } } coutres; return 0; }2.思考这道题非常得巧妙先是把各个岛屿分块然后给出编号并在 map 中存入每个编号岛屿块的数量然后依次遍历每个 graph[i][j] 0 的节点假设依次将它们变成陆地然后寻找上下左右是否遇见有编号的岛屿块如果有就计数并用 set 去重防止重复计数相同编号的岛屿最后取每种情况下的最大值即可。3.Reference104.建造最大岛屿 | 代码随想录