問題概要

下図のようなポリオミノが 3 個与えられる。いずれも 4 × 4 グリッドにおさまるサイズであり、入力は 4 × 4 グリッドで与えられる。文字 '#' に対応する部分が与えられるポリオミノに対応する。

これらのポリオミノに対し

回転は OK
左右や上下への平行移動は OK
裏返しはなし

というルールのもとで、4 × 4 グリッド内部に配置してい。下図のように、はみ出さないように敷き詰めることができるかどうかを判定せよ。

考えたこと

各ポリオミノについて

回転を加味した $4^{3} = 64$ 通りのパターンについて
平行移動をすべて考慮する

という全探索をすれば OK。計算時間は余裕で間に合う。が、実装がとても大変。

今回は、ポリオミノの配置関係をビットで管理することにした。各マスを 0, 1, ..., 15 という番号と対応させると、ポリオミノの配置は $0$ 以上 $65536$ 未満の整数値で表せる。

ビットで考えると、平行移動がとても楽に書ける。整数値 m で表されるポリオミノ配置に対して、下方向に $i$ マス分、右方向に $j$ マス分平行移動して得られる配置 m2 は

m2 = m << (i * 4 + j)

と求められる。ただし、そもそもこの移動によってはみ出す場合は、このはみ出したマスが一周回って登場するようなことになってしまうために注意。

また、

2 つのポリオミノ配置 m1 と m2 が重なるかどうかの判定：if (m1 & m2) { }
3 つのポリオミノ配置 m1, m2, m3 を並べて 16 マスを覆えるかの判定：if ((m1 | m2 | m3) == (1 << 16) - 1) { }

というようにできる。

コード

ここでは、for 文をネストする方式で実装した。

#include <bits/stdc++.h>
using namespace std;

// ミノ mino を右に 90 度回転する (マス (i, j) -> (j, 3 - i))
int rotate(int mino) {
    int res = 0;
    for (int i = 0; i < 4; ++i) {
        for (int j = 0; j < 4; ++j) {
            if (mino & (1 << (i * 4 + j))) res |= 1 << (j * 4 + (3 - i));
        }
    }
    return res;
}

// mino を、上下に di マス、左右に dj マスの移動が可能かどうか (はみ出さないか) を判定する
bool can_move(int mino, int di, int dj) {
    int mini = 4, maxi = -1, minj = 4, maxj = -1;
    for (int i = 0; i < 4; ++i) {
        for (int j = 0; j < 4; ++j) {
            if (mino & (1 << (i * 4 + j))) {
                mini = min(mini, i), maxi = max(maxi, i);
                minj = min(minj, j), maxj = max(maxj, j);
            }
        }
    }
    return (mini + di >= 0 && maxi + di < 4 && minj + dj >= 0 && maxj + dj < 4);
}

// ミノを限界まで左上に動かす
int move_left_up(int mino) {
    while (can_move(mino, -1, 0)) mino >>= 4;
    while (can_move(mino, 0, -1)) mino >>= 1;
    return mino;
}

int main() {
    // 16 マスすべてを表すフラグ
    int all = (1 << 16) - 1;
    
    // 入力受け取り
    vector<int> m(3, 0);
    for (int id = 0; id < 3; ++id) {
        for (int i = 0; i < 4; ++i) {
            string S;
            cin >> S;
            for (int j = 0; j < 4; ++j) {
                if (S[j] == '#') m[id] |= 1 << (i * 4 + j);
            }
        }
    }
            
    // 3 種のミノの回転をすべて試す
    for (int i = 0; i < 4; ++i, m[0] = rotate(m[0])) {
        for (int j = 0; j < 4; ++j, m[1] = rotate(m[1])) {
            for (int k = 0; k < 4; ++k, m[2] = rotate(m[2])) {
                // 各ミノを限界まで左上に動かしておく
                for (auto &mi : m) mi = move_left_up(mi);
                
                // 各ミノにつき、最大 15 マス分の移動を試す
                vector<int> d(3);
                for (d[0] = 0; d[0] < 15; ++d[0]) {
                    for (d[1] = 0; d[1] < 15; ++d[1]) {
                        for (d[2] = 0; d[2] < 15; ++d[2]) {
                            // はみ出すミノがある場合は false
                            bool can = true;
                            for (int id = 0; id < 3; ++id) {
                                if (!can_move(m[id], d[id] / 4, d[id] % 4)) can = false;
                            }
                            if (!can) continue;
                            
                            // 移動後のミノの位置を求める
                            vector<int> m2(3);
                            for (int id = 0; id < 3; ++id) m2[id] = m[id] << d[id];
                            
                            // ミノに重なりがあったらダメ
                            if ((m2[1] & m2[2]) || (m2[2] & m2[0]) || (m2[0] & m2[1])) continue;
  
                            // ミノが正方形を作れるか
                            if ((m2[0] | m2[1] | m2[2]) == all) {
                                cout << "Yes" << endl;
                                return 0;
                            }
                        }
                    }
                }
            }
        }
    }
    cout << "No" << endl;
}

けんちょんの競プロ精進記録

競プロの精進記録や小ネタを書いていきます

AtCoder ABC 322 D - Polyomino (水色, 400 点)

問題概要

考えたこと

コード