TopCoder SRM 794 : Div1 Easy Div2 Hard IslandInALake

Mediumのポカミスが痛い。
https://community.topcoder.com/stat?c=problem_statement&pm=16620&rd=18405

問題

2次元グリッドで地形が与えられる。
各セルは陸地か水場であり、外周はすべて水場で、4方向の隣接セルで連結された水場は海である。

海でない水場をいくつか陸地で埋めることにしたい。
その際、

• 陸地の連結判定は、4方向ではなく8方向の隣接セルの有無によって行う。
• 新規に埋めた陸地は、既存の陸地と連結しない

を満たすとき、最大の新規陸地の連結成分のマス数を求めよ。

解法

とりあえず海でもなく既存の陸地に隣接しないマスを全部陸地にしてしまおう。
次いでそれらの連結判定を行い、最大のものを取得する。

template<int um> class UF {
	public:
	vector<int> par,rank,cnt;
	UF() {par=rank=vector<int>(um,0); cnt=vector<int>(um,1); for(int i=0;i<um;i++) par[i]=i;}
	void reinit() {int i; FOR(i,um) rank[i]=0,cnt[i]=1,par[i]=i;}
	int operator[](int x) {return (par[x]==x)?(x):(par[x] = operator[](par[x]));}
	int count(int x) { return cnt[operator[](x)];}
	int operator()(int x,int y) {
		if((x=operator[](x))==(y=operator[](y))) return x;
		cnt[y]=cnt[x]=cnt[x]+cnt[y];
		if(rank[x]>rank[y]) return par[x]=y;
		rank[x]+=rank[x]==rank[y]; return par[y]=x;
	}
};

class IslandInALake {
	public:
	int build(vector <string> country) {
		int H=country.size();
		int W=country[0].size();
		int y,x,cy,cx;
		UF<2500> uf;
		UF<2500> uf2;
		FOR(y,H) FOR(x,W) if(country[y][x]=='.') {
			if(y&&country[y-1][x]=='.') uf2(y*50+x,(y-1)*50+x);
			if(x&&country[y][x-1]=='.') uf2(y*50+x,y*50+x-1);
		}
		FOR(y,H) FOR(x,W) if(country[y][x]=='#') {
			for(cy=y-1;cy<=y+1;cy++) {
				for(cx=x-1;cx<=x+1;cx++) if(country[cy][cx]=='.') country[cy][cx]='$';
			}
		}
		
		FOR(y,H) FOR(x,W) if(country[y][x]=='.'&&uf2[0]!=uf2[y*50+x]) {
			for(cy=y-1;cy<=y+1;cy++) {
				for(cx=x-1;cx<=x+1;cx++) if(country[cy][cx]=='.'&&uf2[cy*50+cx]!=uf2[0]) uf(y*50+x,cy*50+cx);
			}
		}
		int ma=0;
		FOR(y,H) FOR(x,W) if(country[y][x]=='.') {
			if(uf2[0]==uf2[y*50+x]) continue;
			ma=max(ma,uf.count(y*50+x));
		}
		//FOR(y,H) cout<<country[y]<<endl;
		return ma;
		
	}
}

まとめ

いまいち何がしたいのかわからなかった問題。