东莞如何建设网站制作平台wordpress主题apok

东莞如何建设网站制作平台,wordpress主题apok,东营房产信息网58同城,杭州建设职业学校官方网站KamaCoder99.岛屿数量 99. 计数孤岛 1.思路 DFS 深搜解法 解决此问题的核心思想是 DFS。当我们遍历网格时#xff0c;每遇到一个未被访问过的陆地#xff08;1#xff09;#xff0c;就意味着发现了一个新的岛屿。此时#xff0c;我们需要从这个点出发#xff0c;通过D…KamaCoder99.岛屿数量99. 计数孤岛1.思路DFS 深搜解法解决此问题的核心思想是DFS。当我们遍历网格时每遇到一个未被访问过的陆地1就意味着发现了一个新的岛屿。此时我们需要从这个点出发通过DFS找到所有与它相连的陆地并将它们全部标记为“已访问”以避免重复计算。方式一main 和 dfs 分工明确。在 main 函数中发现新岛屿后先标记起点 used[i][j] true再调用 dfsdfs 函数 不处理传入的起点只负责标记并递归访问其相邻节点。dfs 函数的正确执行依赖于 main 函数的预处理。如果忘记在main中标记used[i][j]可能会导致无限递归或逻辑错误。#include iostream #include vector using namespace std; int dir[4][2]{0,-1,-1,0,0,1,1,0}; void dfs(vectorvectorintgraph,vectorvectorboolused,int x,int y){ 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]1 !used[nextx][nexty]){ used[nextx][nexty]true; // 只标记并访问邻居 dfs(graph,used,nextx,nexty); } } } int main(){ int n,m;cinnm; vectorvectorint graph(n1,vectorint(m1,0)); vectorvectorbool used(n1,vectorbool(m1,false)); for(int i1;in;i){ for(int j1;jm;j){ cingraph[i][j]; } } int res0; for(int i1;in;i){ for(int j1;jm;j){ if(graph[i][j]1 !used[i][j]){ res; // 遇到没访问过的陆地1 used[i][j]true; // 关键点main负责标记起点 dfs(graph,used,i,j); } } } coutres; return 0; }方式二dfs 高度封装。在 main 函数中发现新岛屿后直接调用 dfs由 dfs 内部处理标记dfs 函数先处理传入的起点检查、标记再递归访问其相邻节点。main函数只需要“发现”一个新起点然后把整个探索任务“外包”给dfs。dfs函数没有前置条件自身逻辑完整调用更安全也更容易在其他场景中复用。#include iostream #include vector using namespace std; 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; // 终止条件访问过的节点 或者 遇到海水 used[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; dfs(graph,used,nextx,nexty); } } int main(){ int n,m;cinnm; vectorvectorint graph(n1,vectorint(m1,0)); vectorvectorbool used(n1,vectorbool(m1,false)); for(int i1;in;i){ for(int j1;jm;j){ cingraph[i][j]; } } int res0; for(int i1;in;i){ for(int j1;jm;j){ if(graph[i][j]1 !used[i][j]){ res; dfs(graph,used,i,j); } } } coutres; return 0; }BFS 广搜解法使用 BFS 最重要的一点就是要清楚在什么时候将一个节点标记为usedtrue错误做法从队列中取出节点时再标记。同一个节点可能被多个邻居加入队列导致队列中出现大量重复节点严重影响性能。// 错误示例 while(!que.empty()){ pairint,int cur que.front(); que.pop(); used[cur.first][cur.second] true; // -- 错误的标记时机 for(...){ // ... 检查邻居 ... if(graph[nextx][nexty]1 !used[nextx][nexty]){ que.push({nextx,nexty}); // 邻居A和B可能同时看到C并都把C加入队列 } } }正确做法在将节点加入队列之前就立即标记。一旦一个节点被标记任何其他邻居再看到它时!used[nextx][nexty]条件就不满足从而保证了每个节点最多只被加入队列一次。// 正确示例 if(graph[nextx][nexty]1 !used[nextx][nexty]){ used[nextx][nexty]true; // -- 1. 立即标记 que.push({nextx,nexty}); // -- 2. 再加入队列 }#include iostream #include vector #include queue using namespace std; int dir[4][2]{0,-1,-1,0,0,1,1,0}; void bfs(vectorvectorintgraph,vectorvectorboolused,int x,int y){ queuepairint,int que; que.push({x,y}); used[x][y]true; // 只要加入队列立刻标记 while(!que.empty()){ pairint,int cur que.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 !used[nextx][nexty]){ used[nextx][nexty]true; // 只要加入队列立刻标记 que.push({nextx,nexty}); } } } } int main(){ int n,m;cinnm; vectorvectorint graph(n1,vectorint(m1,0)); vectorvectorbool used(n1,vectorbool(m1,false)); for(int i1;in;i){ for(int j1;jm;j){ cingraph[i][j]; } } int res0; for(int i1;in;i){ for(int j1;jm;j){ if(graph[i][j]1 !used[i][j]){ res; bfs(graph,used,i,j); } } } coutres; return 0; }2.思考方式一隐式终止条件函数本身不包含对当前节点的终止检查假定传入的节点是有效的。终止条件的实现是通过在递归调用之前严格“过滤”掉所有无效的下一步来完成的。如果没有任何一个邻居满足递归条件for循环会正常结束函数自然返回从而实现了终止。方式二显式终止条件函数在执行任何实质性操作之前首先检查当前状态是否满足递归继续的条件。如果不满足就立即终止return不再向下执行。特性BFS (队列实现)DFS (递归实现)核心结构while循环 queue递归函数调用隐式栈标记时机入队时标记递归前标记或在递归函数内部处理遍历路径一层一层逐层扩散。一条路走到黑再回溯。空间风险队列可能很大岛屿很宽时。递归可能很深岛屿很长时有栈溢出风险。代码风格迭代逻辑更“平铺直叙”。递归代码更简洁。3.Reference99. 岛屿数量 | 代码随想录KamaCoder100.最大岛屿的面积100. 最大岛屿的面积1.思路DFS写法一隐式终止条件DFS 处理当前节点的相邻节点即在主函数遇到岛屿就计数为1DFS 处理接下来的相邻陆地#include iostream #include vector using namespace std; int res; int dir[4][2]{0,-1,-1,0,0,1,1,0}; void dfs(vectorvectorintgraph,vectorvectorboolused,int x,int y){ 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]1 !used[nextx][nexty]){ res; used[nextx][nexty]true; dfs(graph,used,nextx,nexty); } } } int main(){ int n,m;cinnm; vectorvectorintgraph(n1,vectorint(m1,0)); vectorvectorboolused(n1,vectorbool(m1,false)); int ans0; for(int i1;in;i){ for(int j1;jm;j){ cingraph[i][j]; } } for(int i1;in;i){ for(int j1;jm;j){ if(graph[i][j]1 !used[i][j]){ res1; // 因为dfs处理下一个节点所以这里遇到陆地了就先计数dfs处理接下来的相邻陆地 used[i][j]true; dfs(graph,used,i,j); // 将与其链接的陆地都标记上 true ansmax(ans,res); } } } coutans; return 0; }写法二显式终止条件DFS 处理当前节点即在主函数遇到岛屿就计数为0DFS 处理接下来的全部陆地#include iostream #include vector using namespace std; int res; 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; used[x][y]1; // 标记访问过 res; 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)); vectorvectorboolused(n1,vectorbool(m1,false)); int ans0; for(int i1;in;i){ for(int j1;jm;j){ cingraph[i][j]; } } for(int i1;in;i){ for(int j1;jm;j){ if(graph[i][j]1 !used[i][j]){ res0; // 因为dfs处理当前节点所以遇到陆地计数为0进dfs之后在开始从1计数 dfs(graph,used,i,j); // 将与其链接的陆地都标记上 true ansmax(ans,res); } } } coutans; return 0; }BFS每次开始探索一个新的岛屿时面积计数器都会从1开始重新计算#include iostream #include vector #include queue using namespace std; int res; int dir[4][2]{0,-1,-1,0,0,1,1,0}; void bfs(vectorvectorintgraph,vectorvectorboolused,int x,int y){ queuepairint,intque; que.push({x,y}); used[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[nextx][nexty]1 !used[nextx][nexty]){ res; used[nextx][nexty]true; que.push({nextx,nexty}); } } } } int main(){ int n,m;cinnm; vectorvectorintgraph(n1,vectorint(m1,0)); vectorvectorboolused(n1,vectorbool(m1,false)); int ans0; for(int i1;in;i){ for(int j1;jm;j){ cingraph[i][j]; } } for(int i1;in;i){ for(int j1;jm;j){ if(graph[i][j]1 !used[i][j]){ res1; bfs(graph,used,i,j); // 将与其链接的陆地都标记上 true ansmax(ans,res); } } } coutans; return 0; }2.思考这道题在 岛屿数量 这道题上整体思路没有变化只是把计算的岛屿数量改成了计算最大的某个岛屿思路还是很清晰的重点掌握 DFS 的两种解法要么使用隐式终止条件要么使用显式终止条件二者在主函数中调用前 res 的初始化也是不同的。3.Reference100. 岛屿的最大面积 | 代码随想录