Codeforces #297 Div2 D. Arthur and Walls

これは発想ゲーっぽいが、思いつけてよかった。
http://codeforces.com/contest/525/problem/D

問題

N*Wのグリッドが与えられる。
各セルは埋まっているかフリースペースかである。

このグリッドのフリースペースのうち、隣接セルを通じて連結したセル同士が長方形を成すようにしたい。
そのため埋まったセルを壊してフリースペースにすることができる。

条件を満たすために壊すセル数が最小となる壊し方を求め、その後のグリッドの状態を図示せよ。

解法

以下のように2*2マス中1マスだけ埋まっているという状態がある場合、それを壊していけば良い。

.. .* *. ..
.* .. .. .*.

あとはキューを使い、壊したセルがあればその周辺が上記2*2の状態になっていないか再度チェックしていけば良い。

int H,W;
string S[2020];

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	queue<int> Q;
	cin>>H>>W;
	FOR(y,H) {
		cin>>S[y];
		FOR(x,W) if(S[y][x]=='.') Q.push(y*2000+x);
	}
	
	while(Q.size()) {
		int k=Q.front();
		int ty=k/2000,tx=k%2000;
		Q.pop();
		FOR(i,9) {
			int cy=ty-1+i/3;
			int cx=tx-1+i%3;
			if(cy<0 || cy>=H || cx<0 || cx>=W) continue;
			if(S[cy][cx]=='*') continue;
			
			if(cy>0 && cx>0 && S[cy-1][cx-1]=='*' && S[cy-1][cx]=='.' && S[cy][cx-1]=='.') {
				S[cy-1][cx-1]='.';
				Q.push((cy-1)*2000+(cx-1));
			}
			if(cy<H-1 && cx>0 && S[cy+1][cx-1]=='*' && S[cy+1][cx]=='.' && S[cy][cx-1]=='.') {
				S[cy+1][cx-1]='.';
				Q.push((cy+1)*2000+(cx-1));
			}
			if(cy>0 && cx<W-1 && S[cy-1][cx+1]=='*' && S[cy-1][cx]=='.' && S[cy][cx+1]=='.') {
				S[cy-1][cx+1]='.';
				Q.push((cy-1)*2000+(cx+1));
			}
			if(cy<H-1 && cx<W-1 && S[cy+1][cx+1]=='*' && S[cy+1][cx]=='.' && S[cy][cx+1]=='.') {
				S[cy+1][cx+1]='.';
				Q.push((cy+1)*2000+(cx+1));
			}
		}
	}
	
	FOR(y,H) cout<<S[y]<<endl;
}

まとめ

気づいてしまえばあっさりの面白い発想な問題。