Submission #1133422

---

Source Code Expand

#include <bits/stdc++.h>

using namespace std;

const int INF = 1e9;

int n;
map<vector<string>, int> memo;

bool judge(vector<string>& a, char c) {
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			if (a[i][j] != c) return false;
		}
	}
	return true;
}

int solve(vector<string>& a) {
	queue<pair<vector<string>, int> > q;
	q.push(make_pair(a, 0));
	while (!q.empty()) {
		auto p = q.front();
		q.pop();
		if (memo.find(p.first) != memo.end()) continue;
		if (judge(p.first, '.')) continue;
		if (judge(p.first, '#')) return p.second;
		memo[p.first] = p.second;
		for (int i = 0; i < n; i++) {
			for (int j = 0; j < n; j++) {
				vector<string> b(p.first);
				for (int k = 0; k < n; k++) {
					b[k][j] = p.first[i][k];
				}
				if (memo.find(b) != memo.end()) continue;
				if (judge(b, '.')) continue;
				q.push(make_pair(b, p.second + 1));
			}
		}		
	}
	return INF;
}

int main() {
	cin.tie(0);
	ios::sync_with_stdio(false);
	cin >> n;
	if (n > 3) return 0;
	vector<string> a(n);
	for (int i = 0; i < n; i++) cin >> a[i];
	int ans = solve(a);
	cout << (ans == INF ? -1 : ans) << endl;
	return 0;
}

Submission Info

Judge Result