Day51_图论2.md

岛屿数量

问题描述

给定一个由“0”代表水和“1”代表陆地的二维网格，计算网格中岛屿的数量。

DFS实现

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

BFS实现

通过队列遍历上下左右四个方向，如果是个岛屿，就放入队列并标记用过。如果队列还没有空，就弹出队头元素遍历其上下左右四个方向。

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

岛屿的最大面积

DFS实现

https://kamacoder.com/problempage.php?pid=1172