poj3620

#include<iostream>
#include<string>
#include<stack>
#include<vector>
#include<queue>
#include<cstdio>
using namespace std;
int max(int a,int b){
return a>b?a:b;
}
int a[110][110],vis[111][111];
int N,M,K;
int dfs(int x,int y){ //求得点块的大小 
int z=1;
if(a[x][y]==0) return 0;
vis[x][y]=1;
if(x-1>0&&!vis[x-1][y]) z+=dfs(x-1,y);
if(y-1>0&&!vis[x][y-1]) z+=dfs(x,y-1);
if(x+1<=N&&!vis[x+1][y]) z+=dfs(x+1,y);
if(y+1<=M&&!vis[x][y+1]) z+=dfs(x,y+1);
return z;
}

struct Node{int x,y;};
int dx[]={0,-1,0,1};
int dy[]={-1,0,1,0};
int bfs(int X,int Y){
int i,val=0;
Node now;
now.x=X , now.y=Y;
queue<Node>q;
q.push(now);
vis[X][Y]=1;
while(!q.empty()){
Node u=q.front();q.pop();
val++; //计数
for(i=0;i<4;i++){ //四个方向的查找
Node v;
v.x=dx[i]+u.x;
v.y=dy[i]+u.y;
if(v.x<1 || v.x>N) continue;
if(v.y<1 || v.y>M) continue;
if(!vis[v.x][v.y]&&a[v.x][v.y]==1){
q.push(v); //加入队列
vis[v.x][v.y]=1; //标记为访问过
}
}
}
return val;
}
int main(){
cin>>N>>M>>K;
int i,j;
for(i=0;i<K;i++){
int x,y;
scanf("%d%d",&x,&y);
a[x][y]=1;
}
int ans=0;
for(i=1;i<=N;i++){
for(j=1;j<=M;j++){
if(a[i][j]==1&&!vis[i][j]){
ans=max(ans,bfs(i,j));
}
}
}
printf("%d ",ans);
return 0;
}

原文地址:https://www.cnblogs.com/apple-apple-apple/p/3781912.html