Submission #6505288

---

Source Code Expand

#include <iostream>
#include <vector>
#include <string>
#include <algorithm>

using namespace std;

bool valid(vector<int>& q, int i, int dx, int dy)
{
	int N = q.size();
	int x = q[i];
	int y = i;
	x += dx;
	y += dy;
	while (0 <= x && x < N && 0 <= y && y < N) {
		if (q[y] == x) {
			return false;
		}
		x += dx;
		y += dy;
	}
	return true;
}

bool valid(vector<int>& q, int i)
{
	return valid(q, i, -1, -1)
		&& valid(q, i, 0, -1)
		&& valid(q, i, +1, -1);
}

void dfs(vector<int>& q0, vector<int>& q, int i, vector<int>& ans)
{

	if (!ans.empty()) {
		return;
	}
	int N = q.size();
	if (i == N) {
		ans = q;
		return;
	}
	if (q0[i] != N) {
		if (valid(q, i)) {
			dfs(q0, q, i + 1, ans);
		}
		else {
			return;
		}
	}
	else {
		for (int k = 0; k < N; ++k) {
			q[i] = k;
			if (valid(q, i)) {
				dfs(q0, q, i + 1, ans);
			}
		}
	}
}

vector<int> solve(vector<string>& c)
{
	int N = c.size();
	vector<int> q0(N), q(N);
	for (int i = 0; i < N; ++i) {
		if (count(c[i].begin(), c[i].end(), 'Q') > 1) {
			return {};
		}
		q0[i] = find(c[i].begin(), c[i].end(), 'Q') - c[i].begin();
	}
	q = q0;
	vector<int> ans;
	dfs(q0, q, 0, ans);
	return ans;
}

int main()
{
	int N = 8;
	vector<string> c(N);
	for (auto& x : c) {
		cin >> x;
	}
	auto ans = solve(c);
	if (ans.empty()) {
		cout << "No Answer" << endl;
	}
	else {
		for (int i = 0; i < N; ++i) {
			string s(N, '.');
			s[ans[i]] = 'Q';
			cout << s << endl;
		}
	}
}

Submission Info

Judge Result