状態空間を上手に削減する系の問題

問題概要

$N$ 種類の長方形形状 ( $H_{i} \times W_{i}$ ) をしたスタンプがある (それぞれ「赤」「緑」「青」の 3 種類がある)。

これらを使って 4 × 4 のグリッド上に所望の模様を作りたい。グリッドからはみ出して押してもよい。スタンプを押すと、押されたマスの色は完全に上書きされる。なお、スタンプの縦横を入れ替えることはできない。

所望のマスを作るために必要なスタンプ回数の最小値を求めよ。

制約

$1 \le N \le 16$

考えたこと

最小回数を求める問題なので、愚直には BFS でできそうだ。でも愚直には考えられる状態数が $4^{16}$ 通りあって多すぎる。

そこで、同一視できる状態はまとめてしまって、考慮する状態数を上手に絞ることを考える (非常によるあるタイプの考え方)。今回は

16 マスのうち、どこがすでに所望の色となっているか

によって状態をまとめることを考える。そうすると $2^{16}$ 通りとなって現実的に扱える。

コード

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

int main() {
    int N;
    while (cin >> N) {
        vector<int> H(N), W(N);
        for (int i = 0; i < N; ++i) cin >> H[i] >> W[i];
        vector<string> sfi(4);
        vector<vector<int>> fi(4, vector<int>(4));
        for (int i = 0; i < 4; ++i) {
            cin >> sfi[i];
            for (int j = 0; j < 4; ++j) {
                if (sfi[i][j] == 'R') fi[i][j] = 0;
                else if (sfi[i][j] == 'G') fi[i][j] = 1;
                else fi[i][j] = 2;
            }
        }

        vector<int> dp(1<<16, -1);
        queue<int> que;
        dp[0] = 0;
        que.push(0);
        while (!que.empty()) {
            int cur = que.front();
            que.pop();
            for (int i = 0; i < N; ++i) {
                for (int sx = -H[i]+1; sx < 4; ++sx) {
                    for (int sy = -W[i]+1; sy < 4; ++sy) {
                        for (int c = 0; c < 3; ++c) {
                            int ncur = cur;
                            for (int x = max(sx, 0); x < min(sx+H[i], 4); ++x) {
                                for (int y = max(sy, 0); y < min(sy+W[i], 4); ++y) {
                                    if (fi[x][y] == c) ncur |= 1<<(x*4+y);
                                    else ncur &= ~(1<<(x*4+y));
                                }
                            }
                            if (dp[ncur] == -1) {
                                dp[ncur] = dp[cur] + 1;
                                que.push(ncur);
                            }
                        }
                    }
                }
            }
        }
        cout << dp[(1<<16)-1] << endl;
    }
}