Mister雑記

競プロやります。

AOJ 2297 「Rectangular Stamps」

onlinejudge.u-aizu.ac.jp

問題

 N個の長方形をしたスタンプがあり、 i個目の大きさは H_i \times W_iである。

 4 \times 4の全てのマスが白いグリッドに、これらのスタンプを押していく。

  • インクの色はRGBの3種類。
  • スタンプにインクを付けて押すと、押された部分の色が全て更新される。
  • 同じスタンプを、色を変えて複数回使うことができる。
  • グリッドをはみ出るように押すことができる(はみ出た部分は無視される)。
  • 縦横を入れ替えて押すことはできない。

指定された模様を作るのに必要な、スタンプを押す回数の最小値を求めよ。

制約

  •  1 \leq N \leq 16
  •  1 \leq H_i, W_i \leq 4

考察

制約からして地道な全探索なのだが、中々上手い方法が思いつかなかった。特に「はみ出て押しても良い」という制約が厄介で、「左上のマスから順にスタンプを押していく」といった戦略が取れない。

そこで「スタンプを押す」という操作を「長方形領域の色を変える」と見ると、選べる長方形領域の数は結構少ない( 16^2未満)ので上の方針が使える。それでも盤面の状態数が 4^{16}であまりにも険しく、結局諦めた。

解説を読むと「各マスの状態を『色が一致しているか否か』で持てば状態数を 2^{16}に抑えられる」とあり、「天才か〜?」となった。のはいいのだが、この問題で難しいのは多分実装の方である。


グリッド全探索系の問題でよくあるように、この問題でもグリッドをbitパターンで持つ必要がある。しかしそうなると「選べる長方形領域」もbitパターンにする必要があり、これがまぁ面倒。

その後BFSをするのだが、無駄に探索の枝刈りをしようとしてバグらせた。結局シンプルに「全ての押し方について、全てのインクの色を試して遷移する」としたら上手く行ったが、とても疲れた......。

実装例

onlinejudge.u-aizu.ac.jp

#include <iostream>
#include <vector>
#include <string>
#include <queue>
#include <set>

using namespace std;

const int INF = 1 << 30;

inline int enc(int x, int y) { return x + y * 4; }

int main() {
    int N;
    cin >> N;

    set<int> paint;  // 選べる長方形領域
    for (int i = 0; i < N; ++i) {
        int H, W;
        cin >> H >> W;

        // 左下を軸に全探索
        for (int lx = -3; lx <= 3; ++lx) {
            for (int ly = -3; ly <= 3; ++ly) {
                int pat = 0;
                for (int dx = 0; dx < H; ++dx) {
                    for (int dy = 0; dy < W; ++dy) {
                        int x = lx + dx, y = ly + dy;
                        if (x < 0 || 4 <= x || y < 0 || 4 <= y) continue;
                        pat |= (1 << enc(x, y));
                    }
                }
                paint.insert(pat);
            }
        }
    }

    vector<string> S(4);
    for (auto& s : S) cin >> s;

    // BFS
    queue<int> que;
    que.push((1 << 16) - 1);

    vector<int> dist(1 << 16, INF);
    dist[(1 << 16) - 1] = 0;

    while (!que.empty()) {
        int v = que.front();
        que.pop();

        // 長方形領域と色を全探索
        for (auto pat : paint) {
            for (char c : string("RGB")) {
                int sv = v;
                for (int x = 0; x < 4; ++x) {
                    for (int y = 0; y < 4; ++y) {
                        if ((pat >> enc(x, y)) & 1) {
                            sv &= ~(1 << enc(x, y));
                            sv |= (S[x][y] != c) << enc(x, y);
                            // 一度bitを消してから、「同じか否か」で書き換える
                            // 同じなら0とする
                        }
                    }
                }

                if (dist[sv] == INF) {
                    dist[sv] = dist[v] + 1;
                    que.push(sv);
                }
            }
        }
    }

    cout << dist[0] << endl;
    return 0;
}

反省

  • 見返したらそこまで実装長くなかった(あるある)。
  • 賢く全探索をしていきたい。