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; } };