南湖的瓜 BFS求连通块

现给出一个n×m的地图，代表小c的瓜地，‘#’代表地雷，‘*’代表西瓜，‘.’代表空地，恶人zzh不能踩到地雷，不然他就被炸死了，恶人zzh能从任意位置开始偷瓜，他也能从任意位置选择离开，但是除了使用技能的时候，他只能上下左右走动。请聪明的你算一算小c最多能被恶人zzh偷多少个西瓜。使用技能可以从任意的位置到任意的位置。

思路：

读完题之后，很容易就有思路，这不就是BFS，遍历每一个起点，扩展连通块最大是多少。取最大的两个连通块加起来。

代码：

  1. #include<bits/stdc++.h>
  2. using namespace std;
  4. struct node{
  5.     int x,y;
  6. };
  8. queue<node> q;
  9. int vis[510][510];
  10. int dx[]={0,1,0,-1};
  11. int dy[]={1,0,-1,0};
  12. int n,m;
  13. char g[510][510];
  14. int bfs(int x,int y){
  15.     while(!q.empty()) q.pop();
  16.     int res=0;
  17.     node temp={x,y};
  18.     q.push(temp);
  19.     vis[x][y]=1;
  20.     while(!q.empty()){
  21.         node now=q.front();
  22. //         cout<<now.x<<" "<<now.y<<endl;
  23.         q.pop();
  24.         if(g[now.x][now.y]=='*') res++;
  25.         for(int i=0;i<4;i++){
  26.             node next;
  27.             next.x=now.x+dx[i];
  28.             next.y=now.y+dy[i];
  29.             if(next.x<0 || next.x>=n || next.y<0 || next.y>=m||g[next.x][next.y]=='#') continue;
  30.             if(vis[next.x][next.y]==0){
  31. //                 cout<<next.x<<" "<<next.y<<endl;
  32.                 vis[next.x][next.y]=true;
  33.                 q.push(next);
  34.             }
  35.         }
  36.     }
  38.     return res;    
  40. }
  42. int main(){
  43.     cin>>n>>m;
  44.     for(int i=0;i<n;i++){
  45.         for(int j=0;j<m;j++){
  46.             cin>>g[i][j];
  47.             vis[i][j]=0;
  48.         }
  49.     }
  50.     vector<int> ans;
  51.     for(int i=0;i<n;i++){
  52.         for(int j=0;j<m;j++){
  53.             if(g[i][j]!='#'&&!vis[i][j]) ans.push_back(bfs(i,j));
  54.         }
  55.     }
  56.     sort(ans.begin(),ans.end());
  57.     if(ans.size()>=2) cout<<ans.back()+ans[ans.size()-2]<<endl;
  58.     else if(ans.size()==1) cout<<ans.back()<<endl;
  59.     else cout<<0<<endl;
  60. }