Red Polyomino [AtCoder Beginner Contest 211 E]

https://atcoder.jp/contests/abc211/tasks/abc211_e

前提知識

• BFS

解説

https://atcoder.jp/contests/abc211/submissions/24516205

入力例3を見ると答えの最大数はあまり大きくないので、正しい候補を列挙すればよさそうに見える。
全探索だろうという方針は見えるかもしれないが、実装が今回は問題だと思う。

状態をビットで表現する

まずは状態管理はbitで管理することにしよう。
64箇所について赤にするかしないか2通りであるが、これはunsigned long longを使えばギリギリ入れ込むことができる。
（signedでもできるんかな？ビットで見る分にはできそうだし、llのままでもいいかも）

BFSで列挙していく

BFSによる遷移をK回行うことで、1回の遷移で隣接マスに着色するようにする。
1回目は隣接判定がいらないので、別途やったほうがいい。
自分の実装では1回目だけ別にしている。

隣接マスを塗る場合は、塗られているマス基準で考えるよりも、次塗ろうとしている場所を全通り試して、
そこの隣接に塗られているマスがあるかどうかを見ていくといい。
ビット演算とマスに対する操作に慣れていればそれほど難しくない。

bfsで列挙していくときはかぶっている状態を何回も評価してしまうと遅くなるので、一般的なqueueではなく
setを使ってqueueの役目をさせた。

最後に残った状態が答えの状態となり、その個数が答え。

typedef unsigned long long ull;
int N, K;
string S[8];
int dx[4] = { 0, 1, 0, -1 }, dy[4] = { -1, 0, 1, 0 };
//---------------------------------------------------------------------------------------------------
void _main() {
    cin >> N >> K;
    rep(i, 0, N) cin >> S[i];

    set<ull> que;
    rep(y, 0, N) rep(x, 0, N) if (S[y][x] == '.') que.insert(1ull << (y * N + x));

    rep(k, 1, K) {
        set<ull> nxt;
        fore(cu, que) {
            rep(y, 0, N) rep(x, 0, N) if (S[y][x] == '.' && !(cu & (1ull << (y * N + x)))) {
                bool ok = false;
                rep(d, 0, 4) {
                    int xx = x + dx[d];
                    int yy = y + dy[d];

                    if (0 <= xx && xx < N && 0 <= yy && yy < N) {
                        if (S[yy][xx] == '.' && (cu & (1ull << (yy * N + xx)))) {
                            ok = true;
                        }
                    }
                }
                if (ok) nxt.insert(cu | (1ull << (y * N + x)));
            }
        }
        swap(que, nxt);
    }

    int ans = que.size();
    cout << ans << endl;
}