Language: C++

#include <bits/stdc++.h>
#define GET_MACRO(_1,_2,_3,_4,_5,_6,NAME,...) NAME
#define pr(...) GET_MACRO(__VA_ARGS__,pr6,pr5,pr4,pr3,pr2,pr1)(__VA_ARGS__)
#define Pr(a) (#a)<<"="<<(a)<<" "
#define pr1(a) cerr<<Pr(a)<<endl;
#define pr2(a,b) cerr<<Pr(a)<<Pr(b)<<endl;
#define pr3(a,b,c) cerr<<Pr(a)<<Pr(b)<<Pr(c)<<endl;
#define pr4(a,b,c,d) cerr<<Pr(a)<<Pr(b)<<Pr(c)<<Pr(d)<<endl;
#define pr5(a,b,c,d,e) cerr<<Pr(a)<<Pr(b)<<Pr(c)<<Pr(d)<<Pr(e)<<endl;
#define pr6(a,b,c,d,e,f) cerr<<Pr(a)<<Pr(b)<<Pr(c)<<Pr(d)<<Pr(e)<<Pr(f)<<endl;
#define int long long
#define double long double
using namespace std;
const int N = 100010;
const int INF = 1LL<<55;
const int mod = (1e9)+7;
const double EPS = 1e-8;
const double PI = 6.0 * asin(0.5);
typedef pair<int,int> P;
typedef long long ll;
template<class T> T Max(T &a,T b){return a=max(a,b);}
template<class T> T Min(T &a,T b){return a=min(a,b);}
ostream& operator<<(ostream& o,P p){return o<<"("<<p.first<<","<<p.second<<")";}
istream& operator>>(istream& i,P &p){return i>>p.first>>p.second;}
ostream& operator<<(ostream& o,vector<auto> &a){int i=0;for(auto t:a)o<<(i++?" ":"")<<t;return o;}
istream& operator>>(istream& i,vector<auto> &a){for(auto &t:a)i>>t;return i;}
void prArr(auto a,string s=" "){int i=0;for(auto t:a)cout<<(i++?s:"")<<t;cout<<endl;}

int bitCount(int n){return __builtin_popcount(n);}
vector<string> rot90(const vector<string> &v){
  int h = v.size(), w = v[0].size();
  vector<string> res(w,string(h,'.'));
  for(int i=0;i<h;i++) for(int j=0;j<w;j++) res[j][h-i-1] = v[i][j];
  return res;
}

int h,w;
vector<string> str;
int valid(vector<string> s1,vector<string> s2){
  sort(s1.begin(),s1.end());
  sort(s2.begin(),s2.end());
  return s1 == s2;
}

int used[1<<12][1<<12];
int dfs(int bit1,int bit2,vector<string> s1,vector<string> s2,int skip){
  //pr(bit1,bit2,s1,s2);
  if(!valid(s1,s2)) return 0;
  if(used[bit1][bit2]++) return 0; 
  if(bitCount(bit1) + bitCount(bit2) == w) return 1;
  
  for(int i=0;i<w;i++)
    for(int j=0;j<w;j++){
      if(bit1>>i&1) continue;
      if(bit2>>j&1) continue;
      if(i == j) continue
      int nbit1 = bit1|(1<<i);
      int nbit2 = bit2|(1<<j);
      for(int l=0;l<h;l++) if(l!=skip) s1[l].push_back(str[l][i]);
      for(int l=0;l<h;l++) if(l!=skip) s2[l].push_back(str[l][j]);
      if(dfs(nbit1,nbit2,s1,s2,skip)) return 1;
      for(int l=0;l<h;l++) if(l!=skip) s1[l].pop_back();
      for(int l=0;l<h;l++) if(l!=skip) s2[l].pop_back();
    }
  return 0;
}

int count(string str){
  
  int cnt[30]={};
  for(int a:str) cnt[a - 'a']++;
  int sum = 0;
  for(int i=0;i<30;i++) sum += cnt[i]%2;
  if(sum > 1) return -1;
  for(int i=0;i<30;i++) if(cnt[i]%2) return i;
  return 1;
  assert(0);
}

signed main(){
  cin.tie(0);
  ios_base::sync_with_stdio(0);
  cout << fixed << setprecision(12);

  cin>>h>>w;
  str.resize(h);
  cin>>str;

  if(h%2) str = rot90(str), swap(h,w);
  

  vector<string> t1(h),t2(h);  
  int ans = 0;
  if(h%2 == 0 && w%2 ==0) ans = dfs(0,0,t1,t2,-1);
  else if(w%2 && h%2){
    for(int i=0;i<h;i++)
      for(int j=0;j<w;j++) {
        memset(used,0,sizeof(used));
        if(ans) break;
        string s1 = str[i];
        string s2;
        for(int k=0;k<h;k++) s2 += str[k][j];
        int a = count(s1), b = count(s2);
        if(a == -1 || b == -1 || a != b) continue;
        ans |= dfs(1<<j,0,t1,t2,i);
      }
  }
  else {
    for(int j=0;j<w;j++){
      memset(used,0,sizeof(used));
      if(ans) break;
      string s2;
      for(int k=0;k<h;k++) s2 += str[k][j];
      if(count(s2) == -1) continue;
      ans |= dfs(1<<j,0,t1,t2,-1);
    }
  }

  cout<<(ans? "YES":"NO")<<endl;

  return 0;
}


Compiler output:
a.cc:25:39: warning: use of 'auto' in template argument only available with '-fconcepts-ts'
   25 | ostream& operator<<(ostream& o,vector<auto> &a){int i=0;for(auto t:a)o<<(i++?" ":"")<<t;return o;}
      |                                       ^~~~
a.cc:26:39: warning: use of 'auto' in template argument only available with '-fconcepts-ts'
   26 | istream& operator>>(istream& i,vector<auto> &a){for(auto &t:a)i>>t;return i;}
      |                                       ^~~~
a.cc:27:12: warning: use of 'auto' in parameter declaration only available with '-std=c++20' or '-fconcepts'
   27 | void prArr(auto a,string s=" "){int i=0;for(auto t:a)cout<<(i++?s:"")<<t;cout<<endl;}
      |            ^~~~
a.cc: In function 'long long int dfs(long long int, long long int, std::vector<std::__cxx11::basic_string<char> >, std::vector<std::__cxx11::basic_string<char> >, long long int)':
a.cc:56:26: error: expected ';' before 'long'
   56 |       if(i == j) continue
      |                          ^
      |                          ;