Submission #3227474

---

Source Code Expand

#include <bits/stdc++.h>
typedef long long i64;
using std::cout;
using std::endl;
using std::cin;

std::vector<std::vector<int>> g;
std::vector<std::string> s, t;
int h, w; 

std::vector<int> vec;
std::vector<bool> used;
bool dfs(int n = 0) {
	if(n == (h + 1) / 2) {
		std::map<std::string, int> mp;
		for(int i = 0; i < w; i++) {
			std::string latte = "";
			for(int j = 0; j < h; j++) {
				latte += s[vec[j]][i];
			}
			mp[latte] += 1; reverse(begin(latte), end(latte));
			mp[latte] -= 1;
		}
		
		for(auto p : mp) if(p.second != 0) return false;
		return true;
	}
	
	for(int i = 0; i < h; i++) {
		if(used[i]) continue;
		for(auto e : g[i]) {
			vec[n] = i;
			vec[h - n - 1] = e;
			used[i] = true;
			used[e] = true;
			if(dfs(n + 1)) return true;
			used[i] = false;
			used[e] = false;
		}
	}
	
	return false;
}

int main(){
	cin >> h >> w; s.resize(h); t.resize(h); g.resize(h);
	for(int i = 0; i < h; i++) {
		cin >> s[i];
		
		t[i] = s[i];
		sort(begin(t[i]), end(t[i]));
	}
	
	for(int i = 0; i < h; i++) {
		for(int j = 0; j < h; j++) {
			if(i == j) continue;
			if(t[i] == t[j]) g[i].push_back(j);
		}
	}
	
	vec.resize(h, 0);
	used.resize(h, false);
	cout << (dfs() ? "YES" : "NO") << endl;
	return 0;
}

Submission Info

Judge Result