Pagini recente » Cod sursa (job #485554) | Cod sursa (job #501971) | Cod sursa (job #2380698) | Cod sursa (job #281524) | Cod sursa (job #987885)
Cod sursa(job #987885)
#include <cstdio>
#include <cstdlib>
#include <ctime>
#include <cassert>
#include <vector>
#include <algorithm>
using namespace std;
vector< pair<int, int> > Queens;
int N;
inline bool ValidArrangement(const vector<int> &primaryDiagonal, const vector<int> &secondaryDiagonal) {
for (const auto &d: primaryDiagonal)
if (d > 1)
return false;
for (const auto &d: secondaryDiagonal)
if (d > 1)
return false;
return true;
}
void Solve() {
if (2 <= N && N <= 3) {
Queens.push_back(make_pair(0, 0));
if (N == 3)
Queens.push_back(make_pair(1, 2));
return;
}
srand(time(0));
vector<int> permutation = vector<int>(N), primaryDiagonal, secondaryDiagonal;
for (int i = 0; i < N; ++i)
permutation[i] = i;
do {
random_shuffle(permutation.begin(), permutation.end());
primaryDiagonal = secondaryDiagonal = vector<int>(2 * N, 0);
for (int i = 0; i < N; ++i) {
++primaryDiagonal[i + permutation[i]];
++secondaryDiagonal[N + i - permutation[i]];
}
for (int i = 0; i < N; ++i) {
for (int j = i + 1; j < N; ++j) {
int ii = permutation[i], jj = permutation[j];
int coefficient = 0;
coefficient += (primaryDiagonal[i + ii] > 1 ? -1 : 0);
coefficient += (secondaryDiagonal[N + i - ii] > 1 ? -1 : 0);
coefficient += (primaryDiagonal[j + jj] > 1 ? -1 : 0);
coefficient += (secondaryDiagonal[N + j - jj] > 1 ? -1 : 0);
coefficient += (primaryDiagonal[i + jj] > 0 ? 1 : 0);
coefficient += (secondaryDiagonal[N - i + jj] > 0 ? 1 : 0);
coefficient += (primaryDiagonal[j + ii] > 0 ? 1 : 0);
coefficient += (secondaryDiagonal[N + j - ii] > 0 ? 1 : 0);
if (coefficient < 0) {
--primaryDiagonal[i + ii];
--secondaryDiagonal[N + i - ii];
--primaryDiagonal[j + jj];
--secondaryDiagonal[N + j - jj];
swap(permutation[i], permutation[j]);
swap(ii, jj);
++primaryDiagonal[i + ii];
++secondaryDiagonal[N + i - ii];
++primaryDiagonal[j + jj];
++secondaryDiagonal[N + j - jj];
}
}
}
} while (!ValidArrangement(primaryDiagonal, secondaryDiagonal));
for (int i = 0; i < N; ++i)
Queens.push_back(make_pair(i, permutation[i]));
}
void Read() {
assert(freopen("dame.in", "r", stdin));
assert(scanf("%d", &N) == 1);
}
void Print() {
assert(freopen("dame.out", "w", stdout));
printf("%d\n", int(Queens.size()));
for (const auto &q: Queens)
printf("%d %d\n", q.first + 1, q.second + 1);
}
int main() {
Read();
Solve();
Print();
return 0;
}