TopCoder SRM 374 Div1 Medium PlayerExtraction

問題

上空からスケートリンクを捉えた写真が与えられる。
この中から、チームの番号がkの人のリストを作成したい。


写真の連続する(上下または左右に隣接する、色が同じである)領域で、色がkであり、面積がthreshold以上の領域をチーム番号がkの人と認識する。


その人の座標は、
その人の画像の領域を全て囲うような軸に平行な長方形のうち、最も小さいものの、中心の座標で定義する。


チーム番号がkの人座標を、x座標の順に、それが同じならy座標の順に並べて出力せよ。

制約条件

画像の幅≦50
高さ≦50
k≦9

方針

定義にしたがって実装する。

ソースコード

const int dy[]={-1,0,1,0},dx[]={0,-1,0,1};
vs P;
int mx,MX,my,MY;
int h,w;
int rec(int y,int x,int k){
	P[y][x]='.';
	mx=min(mx,x); my=min(my,y);
	MX=max(MX,x); MY=max(MY,y);
	int res=1;
	rep(d,4){
		int ny=y+dy[d], nx=x+dx[d];
		if(ny<0||nx<0||ny>=h||nx>=w)continue;
		if(P[ny][nx]-'0'==k)res+=rec(ny,nx,k);
	}
	return res;
}
class PlayerExtraction {
	public:
	vector <string> extractPlayers(vector <string> photo, int k, int threshold) 
	{
		P=photo;
		h=P.size(); w=P[0].size();
		vector<pi> ans;
		rep(i,h)rep(j,w)if(P[i][j]-'0'==k){
			mx=MX=j; my=MY=i;
			int a=rec(i,j,k);
			if(a*4>=threshold)ans.pb(mp(mx+MX+1,my+MY+1));
		}
		sort(all(ans));
		vs res;
		rep(i,ans.size()){
			stringstream ss;
			ss<<ans[i].first<<" "<<ans[i].second;
			res.pb(ss.str());
		}
		return res;
	}
};