Cod sursa(job #2458650)

Utilizator KataIsache Catalina Kata Data 21 septembrie 2019 11:39:11
Problema Problema Damelor Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.2 kb
#include <bits/stdc++.h>
using namespace std;
ifstream fin("damesah.in");
ofstream fout("damesah.out");

bool col[15],diag1[35],diag2[35];
int sol[15];
int n,nr;

void bkt(int k);
bool safe(int k, int i);

int main()
{
    fin>>n;
    bkt(1);
    fout<<nr;
    return 0;
}

void bkt(int k)
{
    int i;
    if(k==n+1)
       {
        nr++;
        if (nr==1)
            {
             for (i=1; i<=n; i++)
                 fout<<sol[i]<<" ";
             fout<<'\n';
            }
        return;
       }

    for (i=1; i<=n; i++)
         if (safe(k,i))
            {
              col[i]=1;
              sol[k]=i;
              if (k>=i)
                  diag1[n-k+i]=1;
              else
                  diag1[n+i-k]=1;
              diag2[k+i-1]=1;

              bkt(k+1);

              col[i]=0;
              if (k>=i)
                  diag1[n-k+i]=0;
              else
                  diag1[n+i-k]=0;
              diag2[k+i-1]=0;
            }
}

bool safe(int k, int i)
{
    if (col[i]) return 0;
    if (k>=i)
        {if(diag1[n-k+i])return 0;}
    else
        if(diag1[n+i-k]) return 0;
    if(diag2[k+i-1]) return 0;
    return 1;
}