Cod sursa(job #2036679)

Utilizator GhSamuelGherasim Teodor-Samuel GhSamuel Data 10 octombrie 2017 22:26:17
Problema Dame Scor 30
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.26 kb
#include <stdio.h>
#include <iostream>

using namespace std;
int n, tabla[1001], diag_l[2001], diag_r[2001], col_up[1001];

int _valid(int x, int y)
{
    if (col_up[y] || diag_l[x - y] || diag_r[x + y])
        return 0;
    return 1;
}

int _back(int ln, int nr_d)
{
    int ok;
    if (nr_d == 0)
        return 1;

    for (int col = 1; col <= n; ++col) {
        ok = 0;
        if(_valid(ln, col)) {
            ok = 1;
            tabla[ln] = col;
            col_up[col] = 1;
            diag_l[ln - col] = 1;
            diag_r[ln + col] = 1;
            if(_back(ln + 1, nr_d - 1))
                return 1;
        }
        tabla[ln] = 0;
        if(ok) {
            col_up[col] = 0;
            diag_l[ln - col] = 0;
            diag_r[ln + col] = 0;
        }
    }
    return 0;
}

int main()
{
    FILE * f = fopen("dame.in", "r");
    FILE * g = fopen("dame.out", "w");
    fscanf(f, "%d", &n);

    if (n == 2 || n == 3) {
        _back(1, n - 1);
        fprintf(g, "%d\n", n - 1);
    }
    else {
        _back(1, n);
        fprintf(g, "%d\n", n);
    }
    for (int i = 1; i <= n; ++i)
    for (int j = 1; j <= n; ++j)
        if (tabla[i] == j)
            fprintf(g, "%d %d\n", i, tabla[i]);
    return 0;
}