SRM 655 DIV1 Easy - BichromePainting
問題
http://community.topcoder.com/stat?c=problem_statement&pm=13709&rd=16415
・２次元のボードがあり、各セルは最初すべて白に塗られている。
・プレイヤーはK*Kの正方形のマスをすべて白か黒に上塗りすることができる。
・最終的なボードの状態が与えられるとき、そのボードの状態にすることができれば
Possible,そうでなければImpossibleを返す。
解き方
状態遷移の問題。SRM 595に似ている。
違いとしては、２次元に拡張されているのと、順番が決まっていない、つまり好きに順番を選べるということ。
まずは最終の状態に着目する。
ここで、K*Kのすべて白か黒で塗られている正方形があった場合、
その前の状態が何であっても最後に上書きすることで、その状態にすることができる。
そのような状態を任意の状態'*'に変換して、最後に全て任意の状態にできれば、
その操作を逆にたどることで再現可能なのでPossibleとなる。
コード
class BichromePainting {
public: string isThatPossible(vector<string> board, int k) {
int h=board.size(),w=board[0].size();
int update=1;
while(update){
update=0;
for(int r=0;r+k-1<h;r++)for(int c=0;c+k-1<w;c++){
int w=0,b=0;
FORE(dr,0,k)FORE(dc,0,k){
if(board[r+dr][c+dc]=='W')w++;
else if(board[r+dr][c+dc]=='B')b++;
}
if(w&&b)continue;
if(w==0&&b==0)continue;
update=1;
FORE(dr,0,k)FORE(dc,0,k)board[r+dr][c+dc]='*';
}
}
FORE(i,0,h)FORE(j,0,w)if(board[i][j]!='*')return "Impossible";
return "Possible";
}
};
public: string isThatPossible(vector<string> board, int k) {
int h=board.size(),w=board[0].size();
int update=1;
while(update){
update=0;
for(int r=0;r+k-1<h;r++)for(int c=0;c+k-1<w;c++){
int w=0,b=0;
FORE(dr,0,k)FORE(dc,0,k){
if(board[r+dr][c+dc]=='W')w++;
else if(board[r+dr][c+dc]=='B')b++;
}
if(w&&b)continue;
if(w==0&&b==0)continue;
update=1;
FORE(dr,0,k)FORE(dc,0,k)board[r+dr][c+dc]='*';
}
}
FORE(i,0,h)FORE(j,0,w)if(board[i][j]!='*')return "Impossible";
return "Possible";
}
};
