TopCoder SRM 732 Div2 Hard TheFlippingGame2

Div1EasyよりDiv2Hardが簡単ってどういうこった。
https://community.topcoder.com/stat?c=problem_statement&pm=14844

問題

２次元グリッドが与えられる。
各マスは

• 埋まっていない
• 白いタイルで埋まっている
• 黒いタイルで埋まっている

のいずれかである。

まず最初に、埋まってないマスを白黒いずれかのマスですべて埋める。
ただし埋める色は全マス同色でなければならない。

その後、あるマスを選択すると、隣接マスで連結する同色のマスをすべて白黒反転する、ということを繰り返す。
全マス同色にするには何回マス選択処理が必要か。

解法

埋める色に関しては白黒２パターン両方試せばよい。
連結成分の色を反転させて全マスの色をそろえるにはテクがあり、１つのマスを選んだら、全マス同色になるまでそこを選択・反転し続けることである。
異なる色の隣接マスの移動コストを1としたとき、全マス同色になるまでの処理回数は、選択したマスから移動するのにコスト最大のマスで決まる。
よってこれはマス間の移動距離を求める問題に還元でき、ダイクストラ法で求めることができる。

問題はどのマスを選択するかだが、元のマス数が少ないので全マスで試せばよい。

class TheFlippingGame2 {
	public:
	int hoge(int H,int W,vector<string> S) {
		int mi=10101;
		int sy,sx,x,y;
		FOR(sy,H) FOR(sx,W) {
			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(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});
					}
				}
			}
			mi=min(mi,ma);
		}
		
		
		return mi+1;
	}
	
	int MinimumMoves(int n, int m, vector <string> x) {
		string S="bw";
		int mi=101010;
		FORR(c,S) {
			vector<string> y=x;
			FORR(s2,y) FORR(c2,s2) if(c2=='e') c2=c;
			mi=min(mi,hoge(n,m,y));
		}
		return mi;
	}
}

まとめ

面白い設定ではあるけども。