SRM 655 div1 easy BichromePainting

左端から順に塗りつぶして考えていくと、テストケースにうまくいかないものがあり、そこから手が出なかった。
最終状態からk*kの正方形領域内に'B'と'W'の一方のみが存在するものがあれば、その領域を'?'で塗りつぶす。以下これを繰り返して最終的にn*n全体が'?'で埋まればPossible。

Topcoderの問題演習量が圧倒的に足りない感じ。

[参照記事]
SRM 655 div1 easy:BichromePainting - mayoko’s diary

class BichromePainting {
public:
bool degenerate(vector<string> &b,int y,int x,int k){
    int n=b.size();
    if(y+k-1>=n || x+k-1>=n) return false;
    char c='?';
    for(int i=y;i<=y+k-1;i++)for(int j=x;j<=x+k-1;j++){
        if(b[i][j]!='?'){
            if(c=='?'){
                c=b[i][j];
            }else if(c!=b[i][j]){
                return false;
            }
        }
    }
    if(c=='?') return false;
    for(int i=y;i<=y+k-1;i++)for(int j=x;j<=x+k-1;j++){
        b[i][j]='?';
    }
    return true;
}

bool isPossible(vector<string> &b){
    int n=b.size();
    REP(y,n)REP(x,n){
        if(b[y][x]!='?') return false;
    }
    return true;
}

string isThatPossible(vector <string> board, int k) {
	int n=board.size();
    bool flag=false;;
    while(1){
        REP(y,n)REP(x,n){
            if(degenerate(board,y,x,k)) flag=true;
        }
        if(!flag) break;
        flag=false;
    }
    if(isPossible(board)) return "Possible";
    else return "Impossible";
}
}