#include <iostream>
#include <fstream>
#include <vector>

using namespace std;

struct Stare
{
    int dim;
    vector<vector<int>> mat;
    Stare(int n)
    {
        mat.resize(n, vector<int>(n));
        dim = n;
    }
};

bool esteRezolvabila(Stare &s)
{
    vector<int> v;
    for(int i = 0; i < s.dim; i++)
        for(int j = 0; j < s.dim; j++)
            v.push_back(s.mat[i][j]);

    int nrInversiuni = 0;
    for(int i = 0; i < v.size(); i++)
    {
        if(v[i] == 0)
            continue;
        for(int j = i + 1; j < v.size(); j++)
            if(v[j] < v[i] && v[j] != 0)
                nrInversiuni++;
    }

    // Caz1: matrice de dimensiune impara => nr inversiuni par
    if(s.dim % 2 == 1)
    {
        return nrInversiuni % 2 == 0;
    }

    int linieSpatiu;
    bool gasit = false;
    int linieSpatiuDeJos = 1;
    for(int i = s.dim - 1; i >= 0 && !gasit; i--)
    {
        for(int j = 0; j < s.dim && !gasit; j++)
            if(s.mat[i][j] == 0)
            {
                linieSpatiu = i + 1;
                gasit = true;
            }

        if(!gasit)
            linieSpatiuDeJos++;
    }

    // Caz2: matrice de dimensiune para si spatiul se afla pe o linie para inumarand de jos in sus (ex: penultima) =>
    //          nr de inversiuni trebuie sa fie impar
    if(linieSpatiuDeJos % 2 == 0)
        return nrInversiuni % 2 == 1;

    // Caz3: matrice de dimensiune para si spatiul se afla pe o linie impara inumarand de jos in sus (ex: ultima, antepenultima) =>
    //          nr de inversiuni trebuie sa fie par
    return nrInversiuni % 2 == 0;

}

vector<Stare> genereazaStari(Stare &parinte)
{
    int iSpatiu = 0;
    int jSpatiu = 0;
    bool gasit = 0;
    for(int i = 0; i < parinte.dim && !gasit; i++)
        for(int j = 0; j < parinte.dim && !gasit; j++)
            if(parinte.mat[i][j] == 0)
            {
                iSpatiu = i;
                jSpatiu = j;
                gasit = true;
            }

    vector<Stare> copii;
    // jos
    int iSpatiuNou = iSpatiu + 1;
    int jSpatiuNou = jSpatiu;
    if(iSpatiuNou < parinte.dim)
    {
        Stare jos(parinte.dim);
        jos.mat = parinte.mat;
        swap(jos.mat[iSpatiu][jSpatiu], jos.mat[iSpatiuNou][jSpatiuNou]);
        copii.push_back(jos);
    }

    // sus
    iSpatiuNou = iSpatiu - 1;
    jSpatiuNou = jSpatiu;
    if(iSpatiuNou >= 0)
    {
        Stare sus(parinte.dim);
        sus.mat = parinte.mat;
        swap(sus.mat[iSpatiu][jSpatiu], sus.mat[iSpatiuNou][jSpatiuNou]);
        copii.push_back(sus);
    }

    // stanga
    iSpatiuNou = iSpatiu;
    jSpatiuNou = jSpatiu - 1;
    if(jSpatiuNou >= 0)
    {
        Stare stanga(parinte.dim);
        stanga.mat = parinte.mat;
        swap(stanga.mat[iSpatiu][jSpatiu], stanga.mat[iSpatiuNou][jSpatiuNou]);
        copii.push_back(stanga);
    }

    // dreapta
    iSpatiuNou = iSpatiu;
    jSpatiuNou = jSpatiu + 1;
    if(jSpatiuNou < parinte.dim)
    {
        Stare dreapta(parinte.dim);
        dreapta.mat = parinte.mat;
        swap(dreapta.mat[iSpatiu][jSpatiu], dreapta.mat[iSpatiuNou][jSpatiuNou]);
        copii.push_back(dreapta);
    }

    return copii;
}

Stare citesteStare(const char numeFisier[])
{
    ifstream fin(numeFisier);

    int n;
    fin >> n;
    Stare s(n);

    for(int i = 0; i < n; i++)
        for(int j = 0; j < n; j++)
            fin >> s.mat[i][j];

    fin.close();
    return s;
}

void afisazaStare(const char numeFisier[], Stare &s)
{
    ofstream fout(numeFisier);

    for(int i = 0; i < s.dim; i++)
    {
        for(int j = 0; j < s.dim; j++)
            fout << s.mat[i][j] << ' ';
        fout << '\n';
    }

    fout.close();
}

bool existaDuplicat(vector<Stare> &stari)
{
    for(int i = 0; i < stari.size(); i++)
        for(int j = i + 1; j < stari.size(); j++)
        {
            if(stari[i].mat == stari[j].mat)
                return true;
        }
    return false;
}

void afisazaStarePeEcran(Stare &s)
{
    for(int i = 0; i < s.dim; i++)
    {
        for(int j = 0; j < s.dim; j++)
            cout << s.mat[i][j] << ' ';
        cout << '\n';
    }
    cout << '\n';
}

int main()
{
    // verificare citire si afisare
    Stare stareInititiala = citesteStare("date.in");
    afisazaStare("date.out", stareInititiala);

    cout << "Starea initiala: " << '\n';
    afisazaStarePeEcran(stareInititiala);

    // verificare existaDuplicat
    Stare s1(2);
    s1.mat = {
        {1, 2},
        {3, 0}
    };
    Stare s2(2);
    s2.mat = {
        {1, 3},
        {2, 0}
    };
    Stare s3(2);
    s3.mat = {
        {1, 2},
        {3, 0}
    };

    vector<Stare> stari = {s1, s2, s3};
    cout << "Exista duplicat: " << existaDuplicat(stari) << '\n';

    // verificare esteRezolvabil
    cout << "Starea initiala este rezovabila: " << esteRezolvabila(stareInititiala) << '\n';

    // verificare genereazaStari
    vector<Stare> copii = genereazaStari(stareInititiala);
    cout << "Stari generate de la starea initiala: \n";
    for(int i = 0; i < copii.size(); i++)
        afisazaStarePeEcran(copii[i]);

    return 0;
}