Submission #2384052

---

Source Code Expand

#include <bits/stdc++.h>
#define FOR(i,k,n)  for(int i = (k);i < (n);++i)
#define REP(i,n)    FOR(i,0,n)
#define ALL(x)      begin(x),end(x)

using namespace std;
using vecint = vector<int>;
using ll = int64_t;

bool is_sym(const string& s, const string &t) {
  int w = s.size();
  REP(i,w) {
    if (s[i] != t[w-i-1]) return false;
  }
  return true;
}

bool isok(const vector<string>& t) {
  int h = t.size();
  int w = t[0].size();
  vector<string> u(h);
  REP(i,h) u[i] = string(w, '.');
  vector<string> rem;
  REP(i,w) {
    string s;
    REP(j,h) s += t[j][i];
    rem.push_back(s);
  }
  int k = 0;
  while (!rem.empty()) {
    bool ok = false;
    FOR(i,1,rem.size()) {
      if (is_sym(rem[0], rem[i])) {
        REP(j,h) {
          u[j][k] = rem[0][j];
          u[j][w-k-1] = rem[i][j];
        }
        ++k;
        ok = true;
        rem.erase(begin(rem) + i);
        break;
      }
    }
    if (!ok) {
      if (is_sym(rem[0], rem[0]) && (w%2) == 1 && u[0][w/2] == '.') {
        REP(j,h) {
          u[j][w/2] = rem[0][j];
        }
      } else {
        return false;
      }
    }
    rem.erase(begin(rem));
  }
  return true;
}

bool solve(const vector<string>& t, int k = 0) {
  int h = t.size();
  if (2*k >= h-1) return isok(t);
  FOR(i,k+1,h-k) {
    vector<string> s = t;
    swap(s[i], s[h-k-1]);
    if (solve(s, k+1)) return true;
  }
  return false;
}

int main()
{
  int h, w;
  cin>>h>>w;
  vector<string> t(h);
  REP(i,h) cin>>t[i];
  bool res = solve(t);
  if (res) {
    cout << "YES" << endl;
  } else {
    cout << "NO" << endl;
  }
  return 0;
}

Submission Info

Judge Result