Submission #19305532

---

Source Code Expand

//bool check(vvi grid){
//    int h = sz(grid);
//    int w = sz(grid[0]);
//    {
//        vvi tmp(w,vi(h));
//        rep(i,h)
//            rep(j,w){
//                tmp[j][i] = grid[i][j];
//            }
//        grid = tmp;
//    }
//    swap(h,w);
//    multiset<vi> rows;
//    rep(i,h)
//        rows.insert(grid[i]);
//    while(sz(rows) >= 2){
//        vi a = min(rows);
//        rows.erase(rows.begin());
//        vi b = a;
//        reverse(all(b));
//        auto it = rows.find(b);
//        if(it != rows.end())
//            rows.erase(it);
//        else{
//            if(a != b)
//                return false;
//        }
//    }
//    if(!rows.empty()){
//        vi a = min(rows);
//        vi b = a;
//        reverse(all(b));
//        if(a != b)
//            return false;
//    }
//    return true;
//}
//bool solve(vvi grid){
//    int n = sz(grid);
//    int half = n/2;
//    sort(all(grid));
//    rep(bm,1<<n){
//        if(__builtin_popcount(bm) != half) continue;
//        vvi tmp;
//        rep(i,n)
//            if(bm&(1<<i))
//                tmp.pb(grid[i]);
//        rep(i,n)
//            if(!(bm&(1<<i)))
//                tmp.pb(grid[i]);
//        do{
//            if(check(tmp))
//                return true;
//
//        }while(next_permutation(tmp.begin()+half,tmp.end()));
//    }
//    return false;
//}
//string __(){
//    int h,w;
//    cin >> h >> w;
//    vvi grid(h,vi(w));
//    rep(i,h)
//        rep(j,w){
//            char c;
//            cin >> c;
//            grid[i][j] = c-'a';
//        }
//    if(!solve(grid))
//        return "NO";
//    {
//        vvi tmp(w,vi(h));
//        rep(i,h)
//            rep(j,w){
//                tmp[j][i] = grid[i][j];
//            }
//        grid = tmp;
//    }
//    if(!solve(grid))
//        return "NO";
//    return "YES";
//}
//
#include <set>
#include <iomanip>
#include <algorithm>
#include <cassert>
#include <vector>
#include <utility>
#include <iostream>
#include <string>
#define pb push_back
#define REP_ZERO_INT(i,r) for(int i = 0; i < (r); ++i)
#define GET_REP_MACRO(_1,_2,_3,_4,NAME,...) NAME
#define rep(...) GET_REP_MACRO(__VA_ARGS__,REP_ANY,REP_INT,REP_ZERO_INT)(__VA_ARGS__)
#define all(v) (v).begin(), (v).end()
#define sz(v) ll(v.size())
#define T1 template<typename T> static
using namespace std;
typedef long long ll;
typedef vector<int> vi;
typedef vector<vi> vvi;
T1 ostream& operator<<(ostream& stream, const vector<T>& t);
T1 istream& read(T, T, istream& = cin);
T1 T min(const multiset<T>& s){
    assert(!s.empty());
    return *s.begin();
}
bool check(vvi grid){
    int h = sz(grid);
    int w = sz(grid[0]);
    {
        vvi tmp(w,vi(h));
        rep(i,h)
            rep(j,w){
                tmp[j][i] = grid[i][j];
            }
        grid = tmp;
    }
    swap(h,w);
    multiset<vi> rows;
    rep(i,h)
        rows.insert(grid[i]);
    while(sz(rows) >= 2){
        vi a = min(rows);
        rows.erase(rows.begin());
        vi b = a;
        reverse(all(b));
        auto it = rows.find(b);
        if(it != rows.end())
            rows.erase(it);
        else{
            if(a != b)
                return false;
        }
    }
    if(!rows.empty()){
        vi a = min(rows);
        vi b = a;
        reverse(all(b));
        if(a != b)
            return false;
    }
    return true;
}
bool solve(vvi grid){
    int n = sz(grid);
    int half = n/2;
    sort(all(grid));
    rep(bm,1<<n){
        if(__builtin_popcount(bm) != half) continue;
        vvi tmp;
        rep(i,n)
            if(bm&(1<<i))
                tmp.pb(grid[i]);
        rep(i,n)
            if(!(bm&(1<<i)))
                tmp.pb(grid[i]);
        do{
            if(check(tmp))
                return true;

        }while(next_permutation(tmp.begin()+half,tmp.end()));
    }
    return false;
}
string __(){
    int h,w;
    cin >> h >> w;
    vvi grid(h,vi(w));
    rep(i,h)
        rep(j,w){
            char c;
            cin >> c;
            grid[i][j] = c-'a';
        }
    if(!solve(grid))
        return "NO";
    {
        vvi tmp(w,vi(h));
        rep(i,h)
            rep(j,w){
                tmp[j][i] = grid[i][j];
            }
        grid = tmp;
    }
    if(!solve(grid))
        return "NO";
    return "YES";
}

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout << fixed << setprecision(15);
        cout << __() << '\n';
}

Submission Info

Judge Result