Cod sursa(job #1567987)
Utilizator | Data | 13 ianuarie 2016 20:41:44 | |
---|---|---|---|
Problema | Problema Damelor | Scor | 100 |
Compilator | cpp | Status | done |
Runda | Arhiva educationala | Marime | 1.26 kb |
#include <iostream>
#include <fstream>
#define nmax 14
using namespace std;
int x[nmax],n,ok,viz[nmax],nrsol;
bool validare(int k)
{
for(int i=1; i<k; i++)
{
if((x[i]-i == x[k]-k) || (x[i]-i == x[k]+k-2*i))
return 0;
}
return 1;
}
void backtracking(int k)
{
if(k>n)
{
if(ok==1)
{
if(n%2==1 && x[1]==n/2+1)
nrsol--;
nrsol+=2;
}
else
{
for(int j=1; j<=n; j++)
cout<<x[j]<<' ';
cout<<'\n';
{
if(n%2==1 && x[1]==n/2+1)
nrsol--;
nrsol+=2;
}
ok=1;
}
}
else
for(int i=1; i<=(k==1? (n%2==1? n/2+1: n/2): n); i++)
{
x[k]=i;
if(!viz[i])
{
if(validare(k))
{
viz[i]=1;
backtracking(k+1);
viz[i]=0;
}
}
}
}
int main()
{
freopen("damesah.in","rt",stdin);
freopen("damesah.out","wt",stdout);
cin>>n;
backtracking(1);
cout<<nrsol<<'\n';
return 0;
}