Cod sursa(job #1000696)

Utilizator AlexandruValeanuAlexandru Valeanu AlexandruValeanu Data 23 septembrie 2013 16:50:19
Problema Dame Scor 10
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.11 kb
#include <iostream>
#include <fstream>
#include <stack>

using namespace std;

const int Nmax = 1004;

stack <int> st;
int v[Nmax];
int uz[Nmax], dluz[Nmax*2], dcuz[Nmax*2];

#define dluz (dluz+Nmax)

int N, done;

ifstream f("dame.in");
ofstream g("dame.out");

void print()
{
    g << N << "\n";

    for ( int i = 0; i < N; ++i )
    {
        g << i + 1 << " " << v[i] + 1 << "\n";
    }

    g << "\n";
}

void bkt( int k )
{
    if ( done )
            return;

    if ( k > N )
    {
        print();
        done = 1;
    }
    else
        for ( int i = 0; i < N; ++i )
        {
            if ( !( uz[i] || dluz[k-i] || dcuz[k+i])) {
                uz[i] = 1, dluz[k-i] = 1, dcuz[k+i] = 1;
                v[k] = i;
                bkt(k+1);
                uz[i] = 0, dluz[k-i] = 0, dcuz[k+i] = 0;
            }
        }
}

int main()
{
    f >> N;

    if ( N == 1 || N == 2 )
    {
        g << "1\n1 1\n";
    }
    else
        if ( N == 3 )
        {
            g << "2\n1 1\n2 3\n";
        }
        else
            bkt( 1 );

    return 0;
}