Pagini recente » Cod sursa (job #2896695) | Cod sursa (job #2797302) | Cod sursa (job #693049) | Cod sursa (job #2725337) | Cod sursa (job #987895)
Cod sursa(job #987895)
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <ctime>
#include <cassert>
#include <vector>
#include <algorithm>
using namespace std;
const int MAX_N = 1000;
vector< pair<int, int> > Queens;
int N, Permutation[MAX_N], PrimaryDiagonal[2 * MAX_N], SecondaryDiagonal[2 * MAX_N];
inline bool ValidArrangement() {
for (int i = 0; i < 2 * N; ++i)
if (PrimaryDiagonal[i] > 1 || SecondaryDiagonal[i] > 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));
for (int i = 0; i < N; ++i)
Permutation[i] = i;
do {
random_shuffle(Permutation, Permutation + N);
memset(PrimaryDiagonal, 0, sizeof(PrimaryDiagonal));
memset(SecondaryDiagonal, 0, sizeof(SecondaryDiagonal));
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], 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());
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;
}