文章目录
- 【99.计数孤岛】
- DFS版本
- BFS版本
- 【100.岛屿的最大面积】
- DFS写法
- BFS写法
【99.计数孤岛】
思路：
用遇到一个没有遍历过的节点陆地，计数器就加一，然后把该节点陆地所能遍历到的陆地都标记上。
在遇到标记过的陆地节点和海洋节点的时候直接跳过。 这样计数器就是最终岛屿的数量。
DFS版本
#include<iostream>#include<vector>usingnamespacestd;intdir[4][2]={0,1,1,0,0,-1,-1,0};// 四个方向voiddfs(constvector<vector<int>>&grid,vector<vector<bool>>&visited,intx,inty){for(inti=0;i<4;i++){intnextx=x+dir[i][0];intnexty=y+dir[i][1];if(nextx<0||nextx>=grid.size()||nexty<0||nexty>=grid[0].size())continue;// 越界了直接跳过if(!visited[nextx][nexty]&&grid[nextx][nexty]==1){visited[nextx][nexty]=true;dfs(grid,visited,nextx,nexty);}}}intmain(){intn,m;cin>>n>>m;vector<vector<int>>grid(n,vector<int>(m,0));vector<vector<bool>>visited(n,vector<bool>(m,false));for(inti=0;i<n;i++){for(intj=0;j<m;j++){cin>>grid[i][j];}}intresult=0;for(inti=0;i<n;i++){for(intj=0;j<m;j++){if(!visited[i][j]&&grid[i][j]==1){visited[i][j]=true;result++;dfs(grid,visited,i,j);}}}cout<<result<<endl;return0;}BFS版本
这里有一个广搜中很重要的细节：
根本原因是只要 加入队列就代表 走过，就需要标记，而不是从队列拿出来的时候再去标记走过。
区别在哪里？
如果从队列拿出节点，再去标记这个节点走过，就会发生下图所示的结果，会导致很多节点重复加入队列。
超时写法 （从队列中取出节点再标记，注意代码注释的地方）
intdir[4][2]={0,1,1,0,-1,0,0,-1};// 四个方向voidbfs(vector<vector<char>>&grid,vector<vector<bool>>&visited,intx,inty){queue<pair<int,int>>que;que.push({x,y});while(!que.empty()){pair<int,int>cur=que.front();que.pop();intcurx=cur.first;intcury=cur.second;visited[curx][cury]=true;// 从队列中取出在标记走过for(inti=0;i<4;i++){intnextx=curx+dir[i][0];intnexty=cury+dir[i][1];if(nextx<0||nextx>=grid.size()||nexty<0||nexty>=grid[0].size())continue;// 越界了，直接跳过if(!visited[nextx][nexty]&&grid[nextx][nexty]=='1'){que.push({nextx,nexty});}}}}加入队列 就代表走过，立刻标记，正确写法： （注意代码注释的地方）
intdir[4][2]={0,1,1,0,-1,0,0,-1};// 四个方向voidbfs(vector<vector<char>>&grid,vector<vector<bool>>&visited,intx,inty){queue<pair<int,int>>que;que.push({x,y});visited[x][y]=true;// 只要加入队列，立刻标记while(!que.empty()){pair<int,int>cur=que.front();que.pop();intcurx=cur.first;intcury=cur.second;for(inti=0;i<4;i++){intnextx=curx+dir[i][0];intnexty=cury+dir[i][1];if(nextx<0||nextx>=grid.size()||nexty<0||nexty>=grid[0].size())continue;// 越界了，直接跳过if(!visited[nextx][nexty]&&grid[nextx][nexty]=='1'){que.push({nextx,nexty});visited[nextx][nexty]=true;// 只要加入队列立刻标记}}}}以上两个版本其实，其实只有细微区别，就是visited[x][y] = true;放在的地方，这取决于我们对 代码中队列的定义，队列中的节点就表示已经走过的节点。所以只要加入队列，立即标记该节点走过。
#include<iostream>#include<vector>#include<queue>usingnamespacestd;intdir[4][2]={0,1,1,0,0,-1,-1,0};// 四个方向voidbfs(constvector<vector<int>>&grid,vector<vector<bool>>&visited,intx,inty){queue<pair<int,int>>que;que.push({x,y});visited[x][y]=true;// 只要加入队列，立即做标记while(!que.empty()){pair<int,int>cur=que.front();que.pop();intcurx=cur.first;intcury=cur.second;for(inti=0;i<4;i++){intnextx=curx+dir[i][0];intnexty=cury+dir[i][1];if(nextx<0||nextx>=grid.size()||nexty<0||nexty>=grid[0].size())continue;if(!visited[nextx][nexty]&&grid[nextx][nexty]==1){que.push({nextx,nexty});visited[nextx][nexty]=true;// 只要加入队列，立即做标记}}}}intmain(){intn,m;cin>>n>>m;vector<vector<int>>grid(n,vector<int>(m,0));vector<vector<bool>>visited(n,vector<bool>(m,false));for(inti=0;i<n;i++){for(intj=0;j<m;j++){cin>>grid[i][j];}}intresult=0;for(inti=0;i<n;i++){for(intj=0;j<m;j++){if(!visited[i][j]&&grid[i][j]==1){result++;bfs(grid,visited,i,j);}}}cout<<result<<endl;return0;}【100.岛屿的最大面积】
DFS写法
#include<iostream>#include<vector>usingnamespacestd;intcount=0;intdir[4][2]={0,1,1,0,0,-1,-1,0};voiddfs(vector<vector<int>>&grid,vector<vector<bool>>&visited,intx,inty){for(inti=0;i<4;i++){intnextx=x+dir[i][0];intnexty=y+dir[i][1];if(nextx<0||nextx>=grid.size()||nexty<0||nexty>=grid[0].size())continue;if(!visited[nextx][nexty]&&grid[nextx][nexty]==1){visited[nextx][nexty]=true;count++;dfs(grid,visited,nextx,nexty);}}}intmain(){intn,m;cin>>n>>m;vector<vector<int>>grid(n,vector<int>(m,0));vector<vector<bool>>visited(n,vector<bool>(m,false));for(inti=0;i<n;i++){for(intj=0;j<m;j++){cin>>grid[i][j];}}intresult=0;for(inti=0;i<n;i++){for(intj=0;j<m;j++){if(!visited[i][j]&&grid[i][j]==1){visited[i][j]=true;count=1;dfs(grid,visited,i,j);result=max(result,count);}}}cout<<result<<endl;return0;}BFS写法
#include<iostream>#include<vector>#include<queue>usingnamespacestd;intcount=0;intdir[4][2]={0,1,1,0,0,-1,-1,0};voidbfs(vector<vector<int>>&grid,vector<vector<bool>>&visited,intx,inty){queue<pair<int,int>>que;que.push({x,y});visited[x][y]=true;count++;while(!que.empty()){pair<int,int>cur=que.front();que.pop();intcurx=cur.first;intcury=cur.second;for(inti=0;i<4;i++){intnextx=curx+dir[i][0];intnexty=cury+dir[i][1];if(nextx<0||nextx>=grid.size()||nexty<0||nexty>=grid[0].size())continue;if(!visited[nextx][nexty]&&grid[nextx][nexty]==1){que.push({nextx,nexty});visited[nextx][nexty]=true;count++;}}}}intmain(){intn,m;cin>>n>>m;vector<vector<int>>grid(n,vector<int>(m,0));vector<vector<bool>>visited(n,vector<bool>(m,false));for(inti=0;i<n;i++){for(intj=0;j<m;j++){cin>>grid[i][j];}}intresult=0;for(inti=0;i<n;i++){for(intj=0;j<m;j++){if(!visited[i][j]&&grid[i][j]==1){count=0;bfs(grid,visited,i,j);result=max(result,count);}}}cout<<result<<endl;return0;}
