JOI 二次予選 2020 A - ポスター (AOJ 0672) (4Q, 難易度 4)

ちょっと重たい全探索問題

• 問題へのリンク

問題概要

の形に配列された二次元文字列 が与えられる。 に対して、次の操作を繰り返すことで に一致させたい。

• 反時計回りに 90 度回転する (コスト 1)
• 時計回りに 90 度回転する (コスト 1)
• 1 マス選んで文字を変更する (コスト 1)

最小コストを求めよ。

制約

• 

考えたこと

次の 4 つの場合を考えればよい。

---

• 回転を何もせず、 とで異なるマスの文字を変更していく (最初の回転コスト：0)
• 最初に 90 度反時計回りに回転したあと、 とで異なるマスの文字を変更していく (最初の回転コスト：1)
• 最初に 180 度反時計回りに回転したあと、 とで異なるマスの文字を変更していく (最初の回転コスト：2)
• 最初に 90 度時計回りに回転したあと、 とで異なるマスの文字を変更していく (最初の回転コスト：1)

---

これらそれぞれの場合のコストを求めて、それらの最小値を求めればよい。

計算量は となる。

コード

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

// 反時計回りに 90 度回転
vector<string> rotate(const vector<string> &S) {
    int N = S.size();
    vector<string> res(N, string(N, '.'));
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++) {
            res[j][N-i-1] = S[i][j];
        }
    }
    return res;
}

// 異なるマス目の個数を求める
int diff(const vector<string> &S, const vector<string> &T) {
    int N = S.size(), res = 0;
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++) {
            if (S[i][j] != T[i][j]) res++;
        }
    }
    return res;
}

int main() {
    int N;
    cin >> N;
    vector<string> S(N), T(N);
    for (int i = 0; i < N; i++) cin >> S[i];
    for (int i = 0; i < N; i++) cin >> T[i];

    // 回転なし
    int res = diff(S, T);

    // もとの S を反時計回りに 90 度回転する場合を試す
    S = rotate(S);
    res = min(res, diff(S, T) + 1);

    // もとの S を反時計回りに 180 度回転する場合を試す
    S = rotate(S);
    res = min(res, diff(S, T) + 2);

    // もとの S を時計回りに 90 度回転する場合を試す
    S = rotate(S);
    res = min(res, diff(S, T) + 1);
    cout << res << endl;
}