Cod sursa(job #2875305)

Utilizator Tudose_StefanTudose Alexandru Stefan Tudose_Stefan Data 21 martie 2022 13:22:29
Problema Problema Damelor Scor 80
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 3.03 kb
#include <fstream>
#include <vector>
#include <iostream>

using namespace std;

ifstream fin("damesah.in");
ofstream fout("damesah.out");

int dimensiune, i, j, solutii;

void afis(int mregine[13][13], int dimensiune)
{
    for (int i = 0; i < dimensiune; i++)
        for(int j = 0; j < dimensiune; j++)
            if (mregine[i][j])
                fout << j+1 << ' ';
}


void atacpluslinie(int matac[13][13], int i, int j, int dimensiune)
{
    int k;
    for (k = 0; k < j; k++)
        matac[i][k]++;
    for (k = j+1; k < dimensiune; k++)
        matac[i][k]++;

}

void atacpluscoloana(int matac[13][13], int i, int j, int dimensiune)
{
    int k;
    for (k = 0; k < i; k++)
        matac[k][j]++;
    for (k = i + 1; k < dimensiune; k++)
        matac[k][j]++;
}

void atacplusdiagonala(int matac[13][13], int i, int j, int dimensiune)
{
    int a, b;
    for (a = i-1, b = j-1; a >= 0 && b >= 0;a--, b--)
        matac[a][b]++;
    for (a = i-1, b = j+1; a>= 0 && b < dimensiune; a--, b++)
        matac[a][b]++;
    for (a = i+1, b = j+1; a< dimensiune && b < dimensiune; a++, b++)
        matac[a][b]++;
    for (a = i+1, b = j-1; a < dimensiune && b>= 0; a++, b--)
        matac[a][b]++;
}

void atacminuslinie(int matac[13][13], int i, int j, int dimensiune)
{
    int k;
    for (k = 0; k < j; k++)
        matac[i][k]--;
    for (k = j+1; k < dimensiune; k++)
        matac[i][k]--;

}

void atacminuscoloana(int matac[13][13], int i, int j, int dimensiune)
{
    int k;
    for (k = 0; k < i; k++)
        matac[k][j]--;
    for (k = i + 1; k < dimensiune; k++)
        matac[k][j]--;
}
void atacminusdiagonala(int matac[13][13], int i, int j, int dimensiune)
{
    int a, b;
    for (a = i-1, b = j-1; a >= 0 && b >= 0;a--, b--)
        matac[a][b]--;
    for (a = i-1, b = j+1; a>= 0 && b < dimensiune; a--, b++)
        matac[a][b]--;
    for (a = i+1, b = j+1; a< dimensiune && b < dimensiune; a++, b++)
        matac[a][b]--;
    for (a = i+1, b = j-1; a < dimensiune && b>= 0; a++, b--)
        matac[a][b]--;
}

void backu(int mregine[13][13], int matac[13][13], int k, int dimensiune)
{
    for (int i = 0; i< dimensiune; i++)
    {
        mregine[k][i] = 1;
        atacpluslinie(matac, k, i, dimensiune);
        atacpluscoloana(matac, k, i, dimensiune);
        atacplusdiagonala(matac, k, i, dimensiune);

        if (matac[k][i] == 0)
        {
            if (k == dimensiune-1)
            {
                solutii++;
                if (solutii == 1)
                    afis(mregine, dimensiune);
            }
            else
                backu(mregine, matac, k+1, dimensiune);
        }
        mregine[k][i] = 0;
        atacminuslinie(matac, k, i, dimensiune);
        atacminuscoloana(matac, k, i, dimensiune);
        atacminusdiagonala(matac, k, i, dimensiune);
    }
}

int matac[13][13], mregine[13][13];
int main()
{
    fin >> dimensiune;
    backu(mregine, matac, 0, dimensiune);
    fout << '\n' << solutii;
    return 0;
}