これは発想ゲーっぽいが、思いつけてよかった。
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; }
まとめ
気づいてしまえばあっさりの面白い発想な問題。