問題概要
$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";
}
};