PKU 3620 Avoid The Lakes
http://poj.org/problem?id=3620
N*MのフィールドにK個の水たまりがある。
このとき、つながっている水たまりの最大の大きさを求めろという問題。
易のほうにはいるんじゃないでしょうか。
BFSしました。
int dx[]={0,1,0,-1}; int dy[]={1,0,-1,0}; bool lake[100][100]; main(){ int n,m,k; cin>>n>>m>>k; rep(i,k){ int a,b; cin>>a>>b; a--,b--; lake[a][b]=true; } int ans=0; rep(i,n){ rep(j,m){ if(lake[i][j]==0)continue; queue<PI> Q; Q.push(mp(i,j)); int tans=0; while(!Q.empty()){ int cx=Q.front().F,cy=Q.front().S;Q.pop(); if(lake[cx][cy]==0)continue; lake[cx][cy]=0; ++tans; rep(k,4){ int nx=cx+dx[k],ny=cy+dy[k]; if(nx<0 || n<=nx || ny<0 || m<=ny || lake[nx][ny]==0)continue; Q.push(mp(nx,ny)); } } ans=max(ans,tans); } } cout<<ans<<endl; }