PKU 3051-Satellite Photographs

問題概要

上下左右のどれかで繋がっている場合島と見做せることにする．
最大の大きさの島を求めよ

解法

BFS

実装(C++)

#include <cstdio>
#include <algorithm>
#include <queue>
using namespace std;
typedef pair<int,int> P;
int H,W;
char MAP[1000][82];
int d[4]={1,0,-1,0};
int solve(int x,int y){
	queue<P> que;que.push(P(x,y));
	int ans=1;
	MAP[x][y]='.';
	while(!que.empty()){
		P t=que.front();que.pop();
		for(int k=0;k<4;k++){
			int nx=t.first+d[k],ny=t.second+d[k^1];
			if(nx>=0&&nx<W&&ny>=0&&ny<H&&MAP[nx][ny]=='*'){
				MAP[nx][ny]='.';
				ans++;
				que.push(P(nx,ny));
			}
		}
	}
	return ans;
}
int main() {
	scanf("%d%d",&H,&W);
	for(int i=0;i<W;i++){
		scanf("%s",MAP[i]);
	}
	int ans=0;
	for(int y=0;y<H;y++){
		for(int x=0;x<W;x++){
			if(MAP[x][y]=='*'){
				ans=max(solve(x,y),ans);
			}
		}
	}
	printf("%d\n",ans);
	return 0;
}