問題概要

$N \times N$のグリッドが白色に塗られている.

$K \times K$のグリッドを塗れる白色と黒色のブラシを持っているとき, 与えられたグリッドのように塗れるか判定しなさい.

制約

  • $1 \leq N \leq 20$
  • $1 \leq K \leq N$

考察

塗れると仮定する.

すると, 最終状態では同じ色で塗られている$K \times K$の領域が存在する必要がある.

その領域は最後に塗ってよく, それを塗る前はどのように塗られていても良い.

言い換えると, その領域は白でも黒でも良いということである. よってその部分を何か別の文字(ここでは?)で置き換え, それ以降の操作では白黒どちらとも代替可能であるとしてよい.

この操作をするごとに, 同じ色で塗られている$K \times K$の領域が増え, 最終的には全てが?になる.

塗れない場合は, 途中で操作が終了し, 盤面に白か黒が残る.

提出コード(C++🔆)

struct BichromePainting {
    vector<string> board;
    int k, N;
    string isThatPossible(vector<string> _board, int _k) {
        board = _board, k = _k;
        N = board.size();
        bool finish;
        do {
            finish = true;
            REP(i, N - k + 1) REP(j, N - k + 1) {
                int b = 0, w = 0;
                REP(p, k) REP(q, k) {
                    if (board[i + p][j + q] == 'B') ++b;
                    if (board[i + p][j + q] == 'W') ++w;
                }
                if (b == 0 and w == 0) continue;
                if (b != 0 and w != 0) continue;
                REP(p, k) REP(q, k) {
                    board[i + p][j + q] = '?';
                }
                finish = false;
            }
        } while (not finish);
        REP(i, N) REP(j, N) if (board[i][j] != '?') return "Impossible";
        return "Possible";
    }
};