TopCoder SRM 732 Div1 Easy TileFlippingGame

こっちの方が難しい。
https://community.topcoder.com/stat?c=problem_statement&pm=14843

問題

基本的にDiv2Hardと同じ。
ただし最初に空きマスを埋める処理を行わない。
TopCoder SRM 732 Div2 Hard TheFlippingGame2 - kmjp's blog

解法

空きマスを埋めないため、Div2Hardでやったようなことを各連結成分毎に行い、その和を取る。
一つ注意点があって、全連結成分の色をそろえなければいけないので、各成分で白・黒それぞれにそろえる場合の最小値を覚えておく必要がある。

template<int um> class UF {
	public:
	vector<int> par,rank;
	UF() {rank=vector<int>(um,0); for(int i=0;i<um;i++) par.push_back(i);}
	int operator[](int x) {return (par[x]==x)?(x):(par[x] = operator[](par[x]));}
	int operator()(int x,int y) {
		if((x=operator[](x))==(y=operator[](y))) return x;
		if(rank[x]>rank[y]) return par[x]=y;
		rank[x]+=rank[x]==rank[y]; return par[y]=x;
	}
};

class TileFlippingGame {
	public:
	int HowManyMoves(int H,int W,vector<string> S) {
		UF<400> uf;
		int mi[400][2]={};
		int sy,sx,x,y;
		
		FOR(sy,H) FOR(sx,W) if(S[sy][sx]!='e') {
			mi[sy*20+sx][0]=mi[sy*20+sx][1]=101010;
			if(sy+1<H&&S[sy+1][sx]!='e') uf(sy*20+sx,(sy+1)*20+sx);
			if(sx+1<W&&S[sy][sx+1]!='e') uf(sy*20+sx,sy*20+sx+1);
		}
		
		FOR(sy,H) FOR(sx,W) if(S[sy][sx]!='e') {
			int D[20][20];
			FOR(y,H) FOR(x,W) D[y][x]=4040;
			priority_queue<pair<int,int>> Q;
			D[sy][sx]=0;
			Q.push({0,sy*100+sx});
			int ma=0;
			while(Q.size()) {
				int co=-Q.top().first;
				int cy=Q.top().second/100;
				int cx=Q.top().second%100;
				Q.pop();
				if(co!=D[cy][cx]) continue;
				ma=max(ma,co);
				
				int d[4]={1,0,-1,0},i;
				FOR(i,4) {
					int ty=cy+d[i];
					int tx=cx+d[i^1];
					if(ty<0||ty>=H||tx<0||tx>=W) continue;
					if(S[ty][tx]=='e') continue;
					if(D[ty][tx]>co+(S[cy][cx]!=S[ty][tx])) {
						D[ty][tx]=co+(S[cy][cx]!=S[ty][tx]);
						Q.push({-D[ty][tx],ty*100+tx});
					}
				}
			}
			if(S[sy][sx]=='b') {
				mi[uf[sy*20+sx]][0]=min(mi[uf[sy*20+sx]][0],ma+((ma%2)));
				mi[uf[sy*20+sx]][1]=min(mi[uf[sy*20+sx]][1],ma+((ma%2)^1));
			}
			else {
				mi[uf[sy*20+sx]][0]=min(mi[uf[sy*20+sx]][0],ma+((ma%2)^1));
				mi[uf[sy*20+sx]][1]=min(mi[uf[sy*20+sx]][1],ma+((ma%2)));
			}
			
			
		}
		int ret[2]={};
		FOR(sy,H) FOR(sx,W) if(uf[sy*20+sx]==sy*20+sx && S[sy][sx]!='e') {
			ret[0]+=mi[sy*20+sx][0];
			ret[1]+=mi[sy*20+sx][1];
		}
		return min(ret[0],ret[1]);
	}
}

まとめ

実装の手間も含めて、こっちDiv2Hardの方がよくない？