Language: C++

#include<bits/stdc++.h>
#define range(i,a,b) for(int i = (a); i < (b); i++)
#define rep(i,b) for(int i = 0; i < (b); i++)
#define all(a) (a).begin(), (a).end()
#define show(x)  cerr << #x << " = " << (x) << endl;
using namespace std;

template<typename T>
ostream& operator << (ostream& os, vector<T>& v){
	rep(i,v.size()){ os << v[i] << (i == v.size() - 1 ? "" : " "); } return os;
}
template<typename T>
istream& operator >> (istream& is, vector<T>& v){
	for(T& x: v){ is >> x; } return is;
}

typedef vector<char> vc;

pair<vc, vc>  getCrossChar(const vector<vc>& s, int i, int j, bool f = 0){
	vc x, y;
	rep(k,s[i].size()){
		x.emplace_back(s[i][k]);
	}

	rep(k,s.size()){
		if(i == k) continue;
		y.emplace_back(s[k][j]);
	}
	sort(all(x));
	if(not f) sort(all(y));

	//cout << x << y << endl;
	return make_pair(x,y);
}

bool check(vector<pair<vc,int>>& c){
	vector<vc> f, s;
	rep(i,c.size() / 2){
		sort(all(c[i].first));
		f.emplace_back(c[i].first);
	}
	range(i,c.size() / 2, c.size()){
		sort(all(c[i].first));
		s.emplace_back(c[i].first);
	}
	sort(all(f));
	sort(all(s));

	rep(i,f.size()){
		rep(j,f[i].size()){
			if(f[i][j] != s[i][j]) return false;
		}
	}
	return true;
}

bool dfs(const vector<vc>& s){
	int h = s.size();
	int w = s[0].size();
	//cout << h << ' ' << w << endl; for(auto i : s){ for(auto j : i){ cout << j; } cout << endl; }

	map<vc, vector<pair<vc,int>>> m;
	rep(i,h){
		rep(j,w){
			pair<vc, vc> p = getCrossChar(s, i, j);
			m[p.first].emplace_back(p.second, i);
		}
	}

	if(m.size() == 1){
		map<vc,int> me;
		rep(i,s.size()){
			sort(all(s[i]));
			me[s[i]]++;
		}

		if(h % 2 == 1){
			int odd = 0;
			for(auto i : me){
				if(i.second % 2 == 1) odd++;
			}
			return odd == 1;
		}else{
			for(auto i : me){
				if(i.second % 2 == 1) return false;
			}
			return true;
		}
	}

	if(h % 2 == 1){
		vector<vc> nxt;
		for(auto i : m){
			if(i.second.size() == w){
				rep(j,w){
					nxt.emplace_back(getCrossChar(s, i.second[0].second, j, 1).second);
				}
			}else{
				if(not check(i.second)) {
					//cout << "kisuu chekcfalse " << endl;
					return false;
				}
			}
		}

		return dfs(nxt);
	}else{
		for(auto i : m){
			if(not check(i.second)) {
				//cout << "guusuu checkfalse" << endl;
				return false;
			}
		}
		return true;
	}
}

int main(){
	int h, w;
	cin >> h >> w;

	vector<vc> s(h, vc(w));
	rep(i,h){
		rep(j,w){
			cin >> s[i][j];
		}
	}

	cout << (dfs(s) ? "YES" : "NO") << endl;
}


Compiler output:
In file included from /usr/include/c++/14/algorithm:61,
                 from /usr/include/x86_64-linux-gnu/c++/14/bits/stdc++.h:51,
                 from a.cc:1:
/usr/include/c++/14/bits/stl_algo.h: In instantiation of 'void std::__insertion_sort(_RandomAccessIterator, _RandomAccessIterator, _Compare) [with _RandomAccessIterator = __gnu_cxx::__normal_iterator<const char*, vector<char> >; _Compare = __gnu_cxx::__ops::_Iter_less_iter]':
/usr/include/c++/14/bits/stl_algo.h:1817:25:   required from 'void std::__final_insertion_sort(_RandomAccessIterator, _RandomAccessIterator, _Compare) [with _RandomAccessIterator = __gnu_cxx::__normal_iterator<const char*, vector<char> >; _Compare = __gnu_cxx::__ops::_Iter_less_iter]'
 1817 |           std::__insertion_sort(__first, __first + int(_S_threshold), __comp);
      |           ~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
/usr/include/c++/14/bits/stl_algo.h:1908:31:   required from 'void std::__sort(_RandomAccessIterator, _RandomAccessIterator, _Compare) [with _RandomAccessIterator = __gnu_cxx::__normal_iterator<const char*, vector<char> >; _Compare = __gnu_cxx::__ops::_Iter_less_iter]'
 1908 |           std::__final_insertion_sort(__first, __last, __comp);
      |           ~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
/usr/include/c++/14/bits/stl_algo.h:4772:18:   required from 'void std::sort(_RAIter, _RAIter) [with _RAIter = __gnu_cxx::__normal_iterator<const char*, vector<char> >]'
 4772 |       std::__sort(__first, __last, __gnu_cxx::__ops::__iter_less_iter());
      |       ~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
a.cc:73:8:   required from here
   73 |                         sort(all(s[i]));
      |                         ~~~~^~~~~~~~~~~
/usr/include/c++/14/bits/stl_algo.h:1782:24: error: assignment of read-only location '__first.__gnu_cxx::__normal_iterator<const char*, std::vector<char> >::operator*()'
 1782 |               *__first = _GLIBCXX_MOVE(__val);
      |                        ^
In file included from /usr/include/c++/14/bits/stl_algo.h:61:
/usr/include/c++/14/bits/stl_heap.h: In instantiation of 'void std::__pop_heap(_RandomAccessIterator, _RandomAccessIterator, _RandomAccessIterator, _Compare&) [with _RandomAccessIterator = __gnu_cxx::__normal_iterator<const char*, vector<char> >; _Compare = __gnu_cxx::__ops::_Iter_less_iter]':
/usr/include/c++/14/bits/stl_algo.h:1596:19:   required from 'void std::__heap_select(_RandomAccessIterator, _RandomAccessIterator, _RandomAccessIterator, _Compare) [with _RandomAccessIterator = __gnu_cxx::__normal_iterator<const char*, vector<char> >; _Compare = __gnu_cxx::__ops::_Iter_less_iter]'
 1596 |           std::__pop_heap(__first, __middle, __i, __comp);
      |           ~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
/usr/include/c++/14/bits/stl_algo.h:1868:25:   required from 'void std::__partial_sort(_RandomAccessIterator, _RandomAccessIterator, _RandomAccessIterator, _Compare) [with _RandomAccessIterator = __gnu_cxx::__normal_iterator<const char*, vector<char> >; _Compare = __gnu_cxx::__ops::_Iter_less_iter]'
 1868 |       std::__heap_select(__first, __middle, __last, __comp);
      |       ~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
/usr/include/c++/14/bits/stl_algo.h:1884:27:   required from 'void std::__introsort_loop(_RandomAccessIterator, _RandomAccessIterator, _Size, _Compare) [with _RandomAccessIterator = __gnu_cxx::__normal_iterator<const char*, vector<char> >; _Size = long int; _Compare = __gnu_cxx::__ops::_Iter_less_iter]'
 1884 |               std::__partial_sort(__first, __last, __last, __comp);
      |               ~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
/usr/include/c++/14/bits/stl_algo.h:1905:25:   required from 'void std::__sort(_RandomAccessIterator, _RandomAccessIterator, _Compare) [with _RandomAccessIterator = __gnu_cxx::__normal_iterator<const char*, vector<char> >; _Compare = __gnu_cxx::__ops::_Iter_less_iter]'
 1905 |           std::__introsort_loop(__first, __last,
      |           ~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~
 1906 |                                 std::__lg(__last - __first) * 2,
      |                                 ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
 1907 |                                 __comp);
      |                                 ~~~~~~~
/usr/include/c++/14/bits/stl_algo.h:4772:18:   required from 'void std::sort(_RAIter, _RAIter) [with _RAIter = __gnu_cxx::__normal_iterator<const char*, vector<char> >]'
 4772 |       std::__sort(__first, __last, __gnu_cxx::__ops::__iter_less_iter());
      |       ~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
a.cc:73:8:   required from here
   73 |                         sort(all(s[i]));
      |                         ~~~~^~~~~~~~~~~
/usr/include/c++/14/bits/stl_heap.h:263:17: error: assignment of read-only location '__result.__gnu_cxx::__normal_iterator<const char*, std::vector<char> >::operator*()'
  263 |       *__result = _GLIBCXX_MOVE(*__first);
      |                 ^
In file included from /usr/include/c++/14/algorithm:60:
/usr/include/c++/14/bits/stl_algobase.h: In instantiation of 'void std::iter_swap(_ForwardIterator1, _ForwardIterator2) [with _ForwardIterator1 = __gnu_cxx::__normal_iterator<const char*, vector<char> >; _ForwardIterator2 = __gnu_cxx::__normal_iterator<const char*, vector<char> >]':
/usr/include/c++/14/bits/stl_algo.h:91:20:   required from 'void std::__move_median_to_first(_Iterator, _Iterator, _Iterator, _Iterator, _Compare) [with _Iterator = __gnu_cxx::__normal_iterator<const char*, vector<char> >; _Compare = __gnu_cxx::__ops::_Iter_less_iter]'
   91 |             std::iter_swap(__result, __b);
      |             ~~~~~~~~~~~~~~^~~~~~~~~~~~~~~
/usr/include/c++/14/bits/stl_algo.h:1855:34:   required from '_RandomAccessIterator std::__unguarded_partition_pivot(_RandomAccessIterator, _RandomAccessIterator, _Compare) [with _RandomAccessIterator = __gnu_cxx::__normal_iterator<const char*, vector<char> >; _Compare = __gnu_cxx::__ops::_Iter_less_iter]'
 1855 |       std::__move_median_to_first(__first, __first + 1, __mid, __last - 1,
      |       ~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
 1856 |                                   __comp);
      |                                   ~~~~~~~
/usr/include/c++/14/bits/stl_algo.h:1889:38:   required from 'void std::__introsort_loop(_RandomAccessIterator, _RandomAccessIterator, _Size, _Compare) [with _RandomAccessIterator = __gnu_cxx::__normal_iterator<const char*, vector<char> >; _Size = long int; _Compare = __gnu_cxx::__ops::_Iter_less_iter]'
 1889 |             std::__unguarded_partition_pivot(__first, __last, __comp);
      |             ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
/usr/include/c++/14/bits/stl_algo.h:1905:25:   required from 'void std::__sort(_RandomAccessIterator, _RandomAccessIterator, _Compare) [with _RandomAccessIterator = __gnu_cxx::__normal_iterator<const char*, vector<char> >; _Compare = __gnu_cxx::__ops::_Iter_less_iter]'
 1905 |           std::__introsort_loop(__first, __last,
      |           ~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~
 1906 |                                 std::__lg(__last - __first) * 2,
      |                                 ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
 1907 |                                 __comp);
      |                                 ~~~~~~~
/usr/include/c++/14/bits/stl_algo.h:4772:18:   required from 'void std::sort(_RAIter, _RAIter) [with _RAIter = __gnu_cxx::__normal_iterator<const char*, vector<char> >]'
 4772 |       std::__sort(__first, __last, __gnu_cxx::__ops::__iter_less_iter());
      |       ~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
a.cc:73:8:   required from here
   73 |                         sort(all(s[i]));
      |                         ~~~~^~~~~~~~~~~
/usr/include/c++/14/bits/stl_algobase.h:185:11: error: no matching function for call to 'swap(const char&, const char&)'
  185 |       swap(*__a, *__b);
      |       ~~~~^~~~~~~~~~~~
In file included from /usr/include/c++/14/bits/stl_pair.h:61,
                 from /usr/include/c++/14/bits/stl_algobase.h:64:
/usr/include/c++/14/bits/move.h:226:5: note: candidate: 'template<class _Tp> std::_Require<std::__not_<std::__is_tuple_like<_Tp> >, std::is_move_constructible<_Tp>, std::is_move_assignable<_Tp> > std::swap(_Tp&, _Tp&)'
  226 |     swap(_Tp& __a, _Tp& __b)
      |     ^~~~
/usr/include/c++/14/bits/move.h:226:5: note:   template argument deduction/substitution failed:
In file included from /usr/include/c++/14/bits/stl_pair.h:60:
/usr/include/c++/14/type_traits: In substitution of 'template<bool _Cond, class _Tp> using std::__enable_if_t = typename std::enable_if::type [with bool _Cond = false; _Tp = void]':
/usr/include/c++/14/type_traits:2323:11:   required by substitution of 'template<class ... _Cond> using std::_Require = std::__enable_if_t<((bool)std::__and_<_Bn>::value)> [with _Cond = {std::__not_<std::__is_tuple_like<const char> >, std::is_move_constructible<const char>, std::is_move_assignable<const char>}]'
 2323 |     using _Require = __enable_if_t<__and_<_Cond...>::value>;
      |           ^~~~~~~~
/usr/include/c++/14/bits/move.h:226:5:   required by substitution of 'template<class _Tp> std::_Require<std::__not_<std::__is_tuple_like<_Tp> >, std::is_move_constructible<_Tp>, std::is_move_assignable<_Tp> > std::swap(_Tp&, _Tp&) [with _Tp = const char]'
  226 |     swap(_Tp& __a, _Tp& __b)
      |     ^~~~
/usr/include/c++/14/bits/stl_algobase.h:185:11:   required from 'void std::iter_swap(_ForwardIterator1, _ForwardIterator2) [with _ForwardIterator1 = __gnu_cxx::__normal_iterator<const char*, vector<char> >; _ForwardIterator2 = __gnu_cxx::__normal_iterator<const char*, vector<char> >]'
  185 |       swap(*__a, *__b);
      |       ~~~~^~~~~~~~~~~~
/usr/include/c++/14/bits/stl_algo.h:91:20:   required from 'void std::__move_median_to_first(_Iterator, _Iterator, _Iterator, _Iterator, _Compare) [with _Iterator = __gnu_cxx::__normal_iterator<const char*, vector<char> >; _Compare = __gnu_cxx::__ops::_Iter_less_iter]'
   91 |             std::iter_swap(__result, __b);
      |             ~~~~~~~~~~~~~~^~~