代码随想录算法训练营Day-50 图论02 | 99.岛屿数量-深搜、99.岛屿数量-广搜 、100.岛屿的最大面积

99.岛屿数量-深搜主函数比较朴素定义基础变量接收数据遍历图节点对每个节点进行处理遇到没访问过的陆地就result然后深搜这篇陆地的上下左右把和这片土地挨着的所有土地标记为访问过也就是把一片岛屿都标记为访问过之后再遍历到这片岛屿的其他陆地节点时就直接跳过了。遍历完之后把所有的新大陆计数并搜索成岛屿最后结果就是岛屿数量了。深搜函数有两种写法一种是终止条件显示写出也就是终止条件判断节点是否访问过以及是否是陆地如果不是陆地或者被访问过那么就return作为终止条件然后在函数逻辑里面只进行下一个节点上下左右是否越界的判断其实也可以把越界判断也放在终止条件里也就是一开始判断xy是否越界下面递归逻辑里的下一个节点就不需要进行判断了。#includeiostream using namespace std; #includevector int dir[4][2]{0,1,1,0,-1,0,0,-1}; void dfs(vectorvectorint grid, vectorvectorbool visited, int x, int y){ if(grid[x][y]0 || visited[x][y]true) return; visited[x][y] true; for(int i0;i4;i){ int nextx xdir[i][0]; int nexty ydir[i][1]; if(nextx0 || nextxgrid.size() || nexty0 || nextygrid[0].size()) continue; dfs(grid, visited, nextx, nexty); } } int main(){ int n,m; cinnm; vectorvectorint grid(n,vectorint(m)); for(int i0;in;i){ for(int j0;jm;j){ cingrid[i][j]; } } vectorvectorbool visited(n,vectorbool(m,false)); int result0; for(int i0;in;i){ for(int j0;jm;j){ if(grid[i][j]1 visited[i][j]0){ result; dfs(grid, visited, i, j); } } } coutresultendl; }一种是终止条件隐式在递归逻辑里面由于只有符合条件索引不越界坐标是陆地且未被访问的节点才会被送入下一层递归所以其实相当于隐含了终止条件。#includeiostream using namespace std; #includevector int dir[4][2]{0,1,1,0,-1,0,0,-1}; void dfs(vectorvectorint grid, vectorvectorbool visited, int x, int y){ for(int i0;i4;i){ int nextx xdir[i][0]; int nexty ydir[i][1]; if(nextx0 || nextxgrid.size() || nexty0 || nextygrid[0].size()) continue; if(grid[nextx][nexty]1 visited[nextx][nexty]false){ visited[nextx][nexty] true; dfs(grid, visited, nextx, nexty); } } } int main(){ int n,m; cinnm; vectorvectorint grid(n,vectorint(m)); for(int i0;in;i){ for(int j0;jm;j){ cingrid[i][j]; } } vectorvectorbool visited(n,vectorbool(m,false)); int result0; for(int i0;in;i){ for(int j0;jm;j){ if(grid[i][j]1 visited[i][j]0){ result; dfs(grid, visited, i, j); } } } coutresultendl; }99.岛屿数量-广搜广搜的主函数逻辑和深搜没变化主要是搜索岛屿的逻辑有一些区别。广搜岛屿首先定义队列然后把起点入队将入队坐标立刻标记为访问过因为入队坐标就是“待搜索周围四方向的中心坐标”因此它本身肯定访问过然后循环直到队为空首先获取队头并弹出然后执行四个方向遍历判断新坐标是否越界是否是陆地且未访问过一旦满足就入队并立刻将坐标标记为访问过。注标记为访问过一定要在入队以后而不是出队时否则会让节点重复入队浪费时间。#includeiostream using namespace std; #includevector #includequeue int dir[4][2]{0,1,1,0,-1,0,0,-1}; void bfs(vectorvectorint grid, vectorvectorbool visited, int x, int y){ queuepairint,int qe; qe.push({x,y}); visited[x][y]true; while(!qe.empty()){ pairint,int pr qe.front();qe.pop(); for(int i0;i4;i){ int nextx pr.firstdir[i][0]; int nexty pr.seconddir[i][1]; if(nextx0 || nextxgrid.size() || nexty0 || nextygrid[0].size()) continue; if(grid[nextx][nexty]1 visited[nextx][nexty]false){ qe.push({nextx,nexty}); visited[nextx][nexty] true; } } } } int main(){ int n,m; cinnm; vectorvectorint grid(n,vectorint(m)); for(int i0;in;i){ for(int j0;jm;j){ cingrid[i][j]; } } vectorvectorbool visited(n,vectorbool(m,false)); int result0; for(int i0;in;i){ for(int j0;jm;j){ if(grid[i][j]1 visited[i][j]0){ result; bfs(grid, visited, i, j); } } } coutresultendl; }100.岛屿的最大面积本题就是在深搜或者广搜函数里加一个计数变量每标记一个岛屿中的新陆地时就加1搜索完之后计数就达到了岛屿的面积。注意在main函数调用搜索函数之前要先把当前遍历到的坐标也就是起点先标记为访问过然后将计数变量初始化为1因为岛屿的面积是从1开始也就是至少为1。#includeiostream using namespace std; #includevector int dir[4][2]{0,1,1,0,-1,0,0,-1}; void dfs(vectorvectorint grid, vectorvectorbool visited, int x, int y, int count){ for(int i0;i4;i){ int nextx xdir[i][0]; int nexty ydir[i][1]; if(nextx0 || nextxgrid.size() || nexty0 || nextygrid[0].size()) continue; if(grid[nextx][nexty]1 visited[nextx][nexty]false){ visited[nextx][nexty] true; count; dfs(grid, visited, nextx, nexty, count); } } } int main(){ int n,m; cinnm; vectorvectorint grid(n,vectorint(m)); for(int i0;in;i){ for(int j0;jm;j){ cingrid[i][j]; } } vectorvectorbool visited(n,vectorbool(m,false)); int result0; for(int i0;in;i){ for(int j0;jm;j){ if(grid[i][j]1 visited[i][j]0){ visited[i][j] true; int newnum 1; dfs(grid, visited, i, j, newnum); result max(result,newnum); } } } coutresultendl; }