AtCoder ABC 307 C - Ideal Sheet (1Q, 水色, 300 点)

とても面倒な全探索問題

• 問題へのリンク

問題概要

サイズが等しいとは限らない 3 つの白黒のグリッド が与えられる。

ある巨大なグリッドに、2 つのグリッド を重ね合わて (黒色部分について OR をとる)、そこから適切に長方形領域を切り出すことで、グリッド に一致させたい。

これが可能であるかどうかを判定せよ。

制約

• 3 つのグリッドの縦の長さ・横の長さはすべて 1 以上 10 以下

考えたこと

切り出すグリッド を基準に考えることにした。グリッド の左上のマスを として、

• グリッド の左上のマスの位置 (マイナスもありうる)
• グリッド の左上のマスの位置 (マイナスもありうる)

を全探索した。具体的には、各グリッドの横や縦の長さの最大値を としたとき、

• グリッド の左上のマスの縦方向の座標： から まで試す
• グリッド の左上のマスの横方向の座標： から まで試す
• グリッド の左上のマスの縦方向の座標： から まで試す
• グリッド の左上のマスの横方向の座標： から まで試す

というようにした。 通りの場合を全探索することとなる。さらに、各方法について、判定に要する計算量は である。よって、全体の計算量は である。

コード

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

int main() {
    int HA, WA, HB, WB, HX, WX;
    cin >> HA >> WA;
    vector<string> A(HA);
    for (int i = 0; i < HA; ++i) cin >> A[i];
    cin >> HB >> WB;
    vector<string> B(HB);
    for (int i = 0; i < HB; ++i) cin >> B[i];
    cin >> HX >> WX;
    vector<string> X(HX);
    for (int i = 0; i < HX; ++i) cin >> X[i];
    
    int maxx = max({HA, HB, HX}), maxy = max({WA, WB, WX});
    bool res = false;
 
    for (int x = -maxx-1; x <= maxx+1; ++x) {
        for (int y = -maxy-1; y <= maxy+1; ++y) {
            for (int x2 = -maxx-1; x2 <= maxx+1; ++x2) {
                for (int y2 = -maxy-1; y2 <= maxy+1; ++y2) {
                    bool ok = true;
                    vector<string> X2(HX, string(WX, '.'));
                    for (int i = 0; i < HA; ++i) {
                        for (int j = 0; j < WA; ++j) {
                            if (A[i][j] == '#') {
                                if (i+x >= 0 && j+y >= 0 && i+x < HX && j+y < WX) X2[i+x][j+y] = '#';
                                else ok = false;
                            }
                        }
                    }
                    for (int i = 0; i < HB; ++i) {
                        for (int j = 0; j < WB; ++j) {
                            if (B[i][j] == '#') {
                                if (i+x2 >= 0 && j+y2 >= 0 && i+x2 < HX && j+y2 < WX) X2[i+x2][j+y2] = '#';
                                else ok = false;
                            }
                        }
                    }
                    
                    if (ok && X2 == X) res = true;
                }
            }
        }
    }
    cout << (res ? "Yes" : "No") << endl;
}