Cod sursa(job #1000694)

Utilizator AlexandruValeanuAlexandru Valeanu AlexandruValeanu Data 23 septembrie 2013 16:48:10
Problema Dame Scor 10
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.22 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[ v[k] ] = 0;
                dluz[k - v[k]] = 0;
                dcuz[k + v[k]] = 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;
}