SRM 655 div1 easy:BichromePainting

SRM655に参加しました。自信なさげにeasyを提出して見事に撃墜され,多少レートが落ちました。
easyは典型問題らしいですね。

問題:TopCoder Statistics - Problem Statement

解法:元の状態からどうやって目的のボードを作るか考えるのではなく,目的のボードからどうやって元のボードを作れるかを考える。例えばk=3のときに
BBBW
BWWW
BWWW
WWWW
(情弱ゆえなんか見にくいのを何とかする方法がわかりませんが許してください)
というボードは,最終的には右下の3*3のWの部分を埋めなければならない。塗る前がどのような状態であったかはどうでも良いので'?'で表すことにすると,最終的な状態の一歩手前は
BBBW
B???
B???
W???
というように表せる。?のところはなんでも良いので,次に
???W
????
????
W???
と遷移させることができる。('?'の中身は
BBW
BBW
WWW
となっていたということですね)
こんな感じでやっていって,最終的に'W'と'?'しか残らなくなったら勝ちです。
以下ソースコード

bool check(const vector<string>& board, int y, int x, int k) {
    char c = '?';
    for (int dy = 0; dy < k; dy++) for (int dx = 0; dx < k; dx++) {
        if (board[y+dy][x+dx] == 'B') {
            if (c != 'W') c = 'B';
            else return false;
        }
        if (board[y+dy][x+dx] == 'W') {
            if (c != 'B') c = 'W';
            else return false;
        }
    }
    if (c == '?') return false;
    return true;
}

class BichromePainting {
public:
    string isThatPossible(vector <string> board, int k) {
        int n = board.size();
        while (1) {
            bool ok = false;
            for (int y = 0; y+k-1 < n; y++) for (int x = 0; x+k-1 < n; x++) {
                if (check(board, y, x, k)) {
                    for (int dy = 0; dy < k; dy++) for (int dx = 0; dx < k; dx++) {
                        board[y+dy][x+dx] = '?';
                    }
                    ok = true;
                }
            }
            if (!ok) break;
        }
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                cout << board[i][j];
            }
            cout << endl;
        }
        for (int i = 0; i < n; i++) for (int j = 0; j < n; j++) {
            if (board[i][j] == 'B') return "Impossible";
        }
        return "Possible";
    }
};