Submission #3621173

---

Source Code Expand

#include <iostream>
#include <iomanip>
#include <cmath>
#include <algorithm>
#include <vector>
#include <queue>
#include <map>
#include <set>
using namespace std;

bool solve(const vector<string> &S, vector<int> &perm){
    int H = S.size();
    int W = S[0].size();
    vector<vector<int>> T(H, vector<int>(W));
    for(int i=0; i<H; i++)
        for(int j=0; j<W; j++)
            T[i][j] = S[perm[i]][j] - 'a';

    //for(int i=0; i<H; i++){
    //    for(int j=0; j<W; j++){
    //        cerr << char('a'+T[i][j]) << " ";
    //    }
    //    cerr << endl;
    //}

    vector<bool> used(W, false);
    for(int i=0; i<W; i++){
        for(int j=i+1; j<W; j++){
            if(used[j]) continue;
            bool ok = true;
            for(int k=0; k<H; k++){
                if(T[k][i] != T[H-1-k][j]){
                    ok = false;
                    break;
                }
            }
            if(ok){
                used[i] = true;
                used[j] = true;
                break;
            }
        }
    }
    int cnt = 0;
    for(int i=0; i<W; i++)
        if(used[i])
            cnt++;

    cnt = W - cnt;

    if(cnt == 0) return true;
    if(cnt > 1) return false;
    int idx = 0;
    for(int i=0; i<W; i++)
        if(!used[i])
            idx = i;
    for(int i=0; i<H; i++)
        if(T[i][idx] != T[H-1-i][idx])
            return false;
    return true;
}



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

    for(int i=0; i<(1<<H); i++){
        if(__builtin_popcount(i) != (H+1)/2) continue;
        vector<string> T;
        for(int j=0; j<H; j++)
            if(i & (1<<j))
                T.push_back(S[j]);
        for(int j=0; j<H; j++)
            if(!(i & (1<<j)))
                T.push_back(S[j]);

        vector<int> perm;
        for(int i=0; i<H; i++)
            perm.push_back(i);
        do{
            if(solve(T, perm)){
                cout << "YES" << endl;
                return 0;
            }
        }while(next_permutation(perm.begin(), perm.begin()+(H+1)/2));
    }
    cout << "NO" << endl;
    return 0;
}

Submission Info

Judge Result