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

99.岛屿数量-深搜

主函数比较朴素：定义基础变量，接收数据，遍历图节点，对每个节点进行处理：遇到没访问过的陆地就result++，然后深搜这篇陆地的上下左右，把和这片土地挨着的所有土地标记为访问过，也就是把一片岛屿都标记为访问过，之后再遍历到这片岛屿的其他陆地节点时就直接跳过了。遍历完之后，把所有的新大陆计数并搜索成岛屿，最后结果就是岛屿数量了。

深搜函数：有两种写法

一种是，终止条件显示写出，也就是终止条件判断节点是否访问过以及是否是陆地，如果不是陆地或者被访问过，那么就return，作为终止条件，然后在函数逻辑里面只进行下一个节点（上下左右）是否越界的判断；

（其实也可以把越界判断也放在终止条件里，也就是一开始判断x，y是否越界，下面递归逻辑里的下一个节点就不需要进行判断了。

#include<iostream> using namespace std; #include<vector> int dir[4][2]={0,1,1,0,-1,0,0,-1}; void dfs(vector<vector<int>>& grid, vector<vector<bool>>& visited, int x, int y){ if(grid[x][y]==0 || visited[x][y]==true) 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>=grid.size() || nexty<0 || nexty>=grid[0].size()) continue; dfs(grid, visited, nextx, nexty); } } int main(){ int n,m; cin>>n>>m; vector<vector<int>> grid(n,vector<int>(m)); for(int i=0;i<n;i++){ for(int j=0;j<m;j++){ cin>>grid[i][j]; } } vector<vector<bool>> visited(n,vector<bool>(m,false)); int result=0; for(int i=0;i<n;i++){ for(int j=0;j<m;j++){ if(grid[i][j]==1 && visited[i][j]==0){ result++; dfs(grid, visited, i, j); } } } cout<<result<<endl; }

一种是，终止条件隐式在递归逻辑里面，由于只有符合条件（索引不越界，坐标是陆地且未被访问）的节点才会被送入下一层递归，所以其实相当于隐含了终止条件。

#include<iostream> using namespace std; #include<vector> int dir[4][2]={0,1,1,0,-1,0,0,-1}; void dfs(vector<vector<int>>& grid, vector<vector<bool>>& visited, int x, int y){ for(int i=0;i<4;i++){ int nextx = x+dir[i][0]; int nexty = y+dir[i][1]; if(nextx<0 || nextx>=grid.size() || nexty<0 || nexty>=grid[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; cin>>n>>m; vector<vector<int>> grid(n,vector<int>(m)); for(int i=0;i<n;i++){ for(int j=0;j<m;j++){ cin>>grid[i][j]; } } vector<vector<bool>> visited(n,vector<bool>(m,false)); int result=0; for(int i=0;i<n;i++){ for(int j=0;j<m;j++){ if(grid[i][j]==1 && visited[i][j]==0){ result++; dfs(grid, visited, i, j); } } } cout<<result<<endl; }

99.岛屿数量-广搜

广搜的主函数逻辑和深搜没变化，主要是搜索岛屿的逻辑有一些区别。

广搜岛屿：首先定义队列，然后把起点入队，将入队坐标立刻标记为访问过（因为入队坐标就是“待搜索周围四方向的中心坐标”，因此它本身肯定访问过），然后循环直到队为空，首先获取队头并弹出，然后执行四个方向遍历，判断新坐标是否越界，是否是陆地且未访问过，一旦满足就入队，并立刻将坐标标记为访问过。

注：标记为访问过一定要在入队以后，而不是出队时，否则会让节点重复入队，浪费时间。

#include<iostream> using namespace std; #include<vector> #include<queue> int dir[4][2]={0,1,1,0,-1,0,0,-1}; void bfs(vector<vector<int>>& grid, vector<vector<bool>>& visited, int x, int y){ queue<pair<int,int>> qe; qe.push({x,y}); visited[x][y]=true; while(!qe.empty()){ pair<int,int> pr = qe.front();qe.pop(); for(int i=0;i<4;i++){ int nextx = pr.first+dir[i][0]; int nexty = pr.second+dir[i][1]; if(nextx<0 || nextx>=grid.size() || nexty<0 || nexty>=grid[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; cin>>n>>m; vector<vector<int>> grid(n,vector<int>(m)); for(int i=0;i<n;i++){ for(int j=0;j<m;j++){ cin>>grid[i][j]; } } vector<vector<bool>> visited(n,vector<bool>(m,false)); int result=0; for(int i=0;i<n;i++){ for(int j=0;j<m;j++){ if(grid[i][j]==1 && visited[i][j]==0){ result++; bfs(grid, visited, i, j); } } } cout<<result<<endl; }

100.岛屿的最大面积

本题就是在深搜或者广搜函数里加一个计数变量，每标记一个岛屿中的新陆地时就加1，搜索完之后计数就达到了岛屿的面积。

注意在main函数调用搜索函数之前，要先把当前遍历到的坐标也就是起点先标记为访问过，然后将计数变量初始化为1，因为岛屿的面积是从1开始，也就是至少为1。

#include<iostream> using namespace std; #include<vector> int dir[4][2]={0,1,1,0,-1,0,0,-1}; void dfs(vector<vector<int>>& grid, vector<vector<bool>>& visited, int x, int y, int& count){ for(int i=0;i<4;i++){ int nextx = x+dir[i][0]; int nexty = y+dir[i][1]; if(nextx<0 || nextx>=grid.size() || nexty<0 || nexty>=grid[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; cin>>n>>m; vector<vector<int>> grid(n,vector<int>(m)); for(int i=0;i<n;i++){ for(int j=0;j<m;j++){ cin>>grid[i][j]; } } vector<vector<bool>> visited(n,vector<bool>(m,false)); int result=0; for(int i=0;i<n;i++){ for(int j=0;j<m;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); } } } cout<<result<<endl; }