E - Symmetric Grid

E - Symmetric Grid

PItS さんのコードを参考にしました
ARC095 E : Symmetric Grid(700) - PItS' Buffer Solution

解法
まず列の並び方を決めた後、全ての行に対応する行があるかを判定する

また、列の並び替えは全て試す必要はなく、ペアを決めるだけでいい

具体的には
p[i] := 列iが持つ実態列j
lock[i] := iが使われているかとして

列iとjをw個目のペアとする時
p[w] = i p[W-1-w] = j
lock[i] = lock[j] = 1
とすればいい

Submission #4359301 - AtCoder Regular Contest 095

vs s;
vvc (ba, 0, 0);
vi p(12), lok(12);
bool check() {
    vb b(12);
    bo m = H & 1;
    rep(h, H) {
        if (b[h])con;
        rep(hr, h + 1, H) {
            if (b[hr])con;
            rep(w, W) {
                if (s[h][p[w]] != s[hr][p[W - 1 - w]])break;
                if (w == W - 1)b[h] = b[hr] = 1;
            }
            if (b[h])bre;
        }
        if (!b[h]) {
            if (m) {
                rep(w, W)if (s[h][p[w]] != s[h][p[W - 1 - w]])return 0;
                m = 0;
            } else {
                return 0;
            }
        }
    }
    return 1;
}

bool pa(int v, int n) {
    if (v == W)return check();
    if (lok[v])return pa(v + 1, n);
    p[n] = v;
    lok[v] = 1;
    rep(r, v + 1, W) {
        if (lok[r])con;
        p[W - 1 - n] = r;
        lok[r] = 1;
        if (pa(v + 1, n + 1))return 1;
        lok[r] = 0;
    }
    lok[v] = 0;
    return 0;
}

void solve() {
    cin >> H >> W;
    na(s, H);
    fill(p, -1);
    if (W % 2) {
        rep(w, W) {
            p[W / 2] = w;
            lok[w] = 1;
            if (pa(0, 0))fYN(1);
            p[W / 2] = -1;
            lok[w] = 0;
        }
        return fYN(0);
    } else {
        fYN(pa(0, 0));
    }
}