ARC095 E Symmetric Grid

問題文

https://beta.atcoder.jp/contests/arc095/tasks/arc095_c

 

まず点対称なグリッドを図示してみると,i番目の行とH-i+1番目の行は反転の関係になっていることがわかる.(Hが奇数の場合,真ん中の行は左右対称になっている).

そこで,列の入れ替え方法を適当に固定したとき,行を入れ替えて点対称に出来るかどうかは,反転の関係になっている行がH/2ペアあるかどうかで判定できることがわかる(Hが奇数のとき,余った行が左右対称かも見る).

問題は列の入れ替え方法が最大12!通りもあって間に合わないことだが,実は本質的に同じ入れ替えがたくさんあるので全て試す必要はない.

例えば2つの文字列abcdeとedcbaがあるとする.このとき対称の位置にある2番目と4番目の文字を入れ替えるとadcbeとebcdaになり,1番目,5番目の文字と2番目,4番目の文字を入れ替えるとbacedとdecabになって,どちらも反転の関係を保っている.

このことから,どの列をペアにする(対称の位置に置く)かだけが本質だとわかって,出来る.

わかってもすっきり書くの難しくない...?

 ソースコード

#include "bits/stdc++.h"
using namespace std;
typedef long long ll;
const ll MOD = 1000000007LL;
char S[12][13];
char T[12][13];
bool used[12];
bool row[12];
int perm[12];
int H, W;
bool check(int c) {
    if (c == W / 2) {
        for (int i = 0; i < W; i++) {
            if (used[i]) continue;
            perm[W / 2] = i;
            break;
        }
        for (int i = 0; i < H; i++) for (int j = 0; j < W; j++) T[i][j] = S[i][perm[j]];
        int cnt = 0;
        memset(row, 0, sizeof(row));
        for (int i = 0; i < H; i++) {
            if (row[i]) continue;
            bool ok = 0;
            for (int j = i + 1; j < H; j++) {
                if (row[j]) continue;
                bool match = 1;
                for (int k = 0; k < W; k++) {
                    if (T[i][k] != T[j][W - 1 - k]) {
                        match = 0;
                        break;
                    }
                }
                if (match) {
                    ok = 1;
                    row[j] = 1;
                    break;
                }
            }
            if (!ok) {
                for (int j = 0; j < W; j++) if (T[i][j] != T[i][W - 1 - j]) return 0;
            }
            else {
                cnt++;
            }
        }
        if (cnt == H / 2) return 1;
        return 0;
    }
    for (int i = 0; i < W; i++) {
        if (used[i]) continue;
        used[i] = 1;
        perm[c] = i;
        for (int j = i + 1; j < W; j++) {
            if (used[j]) continue;
            used[j] = 1;
            perm[W - 1 - c] = j;
            if (check(c + 1)) return 1;
            used[j] = 0;
        }
        used[i] = 0;
    }
    return 0;
}
int main() {
    cin >> H >> W;
    for (int i = 0; i < H; i++) cin >> S[i];
    if (check(0)) cout << "YES" << endl;
    else cout << "NO" << endl;
}