Stamp [第五回 アルゴリズム実技検定 E]

https://atcoder.jp/contests/past202012-open/tasks/past202012_e

解説

https://atcoder.jp/contests/past202012-open/submissions/22282335

実装問題。
要求されていることがかなり複雑なので、適度にモジュール化しないと混乱するかもしれない。
特に目立ったことはしていないが、以下のような関数を利用して解いていく。

• rotateClockwise(T) := 盤面Tを90度回転する（これは既に実装したものを持っていた。提出コード参考）
• shrink(T) := 盤面Tのハンコが無い部分を切り取って最小化する
• isPlacable(T) := 盤面Tを平行移動して置けるかどうか判定する

ハンコを回転と平行移動で置けるかどうかを判定するが、回転は90度回転を3回行うことで
すべての角度で置けるかを試すことで、回転については考えなくてよく、かつ、同じルーチンで判定できる。
shrinkは実装上便利なのでしておいた。
各実装についてはコードを見てもらった方が早いが、特に目立ったアルゴリズムは使っていない。
isPlacableで置けるかどうかも、置く場所を全探索して置けるかを判定している。

int H, W;
string S[10];
//---------------------------------------------------------------------------------------------------
vector<string> shrink(vector<string> T) {
    int min_x = inf, max_x = -1, min_y = inf, max_y = -1;
    rep(y, 0, H) rep(x, 0, W) if (T[y][x] == '#') {
        chmin(min_x, x);
        chmax(max_x, x);
        chmin(min_y, y);
        chmax(max_y, y);
    }

    vector<string> newT;
    rep(y, min_y, max_y + 1) {
        string row = "";
        rep(x, min_x, max_x + 1) row += T[y][x];
        newT.push_back(row);
    }
    return newT;
}
//---------------------------------------------------------------------------------------------------
bool isPlacable(vector<string> T) {
    int HT = T.size(), WT = T[0].size();
    if (H < HT || W < WT) return false;

    rep(sy, 0, H - HT + 1) rep(sx, 0, W - WT + 1) {
        bool ok = true;
        rep(y, 0, HT) rep(x, 0, WT) {
            if (S[y + sy][x + sx] == '#' && T[y][x] == '#') ok = false;
        }
        if (ok) return true;
    }

    return false;
}
//---------------------------------------------------------------------------------------------------
void _main() {
    cin >> H >> W;
    rep(y, 0, H) cin >> S[y];

    vector<string> T(H);
    rep(y, 0, H) cin >> T[y];
    T = shrink(T);

    rep(_, 0, 4) {
        if (isPlacable(T)) {
            cout << "Yes" << endl;
            return;
        }

        T = rotateClockwise(T);
    }

    cout << "No" << endl;
}