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

using namespace std;

enum Direction
{
    None,
    Up,
    Down,
    Left,
    Right
};

struct State
{
    vector<vector<int>> mat;
    int emptySpaceI, emptySpaceJ;      // pozitia spatiului liber
    Direction lastMove;
    State *parent;

    void Resize(int n)
    {
        mat.resize(n, vector<int>(n));
    }
};

void printState(State &state)
{
    for(int i = 0; i < state.mat.size(); i++)
    {
        for(int j = 0; j < state.mat.size(); j++)
            cout << state.mat[i][j] << ' ';
        cout << '\n';
    }
}


// pleaca de la o stare si genereaza cele maixim 4 stari in care se poate ajunge
// (muta spatiul in cele maxim 4 directii)
int diri[] = {1, -1, 0, 0};
int dirj[] = {0, 0, 1, -1};
Direction dir[] = {Down, Up, Right, Left};
vector<State> generateNextStates(State &currentState)
{
    vector<State> nextStates;
    int spaceI = currentState.emptySpaceI;
    int spaceJ = currentState.emptySpaceJ;
    int nextSpaceI, nextSpaceJ;
    int dim = currentState.mat.size();
    for(int i = 0; i < 4; i++)
    {
        // diri[i] = cum se modifica pozitia spatiului pe i
        // dirj[i] = cum se modifica pozitia spatiului pe j
        // dir[i] = in ce directie merg
        nextSpaceI = spaceI + diri[i];
        nextSpaceJ = spaceJ + dirj[i];

        // nextSpaceI si nextSpaceJ sunt inca in matrice
        if(nextSpaceI < 0 || nextSpaceI >= dim ||
            nextSpaceJ < 0 || nextSpaceJ >= dim)
            continue;

        // genereaza noua stare
        State nextState = currentState;
        swap(nextState.mat[spaceI][spaceJ], nextState.mat[nextSpaceI][nextSpaceJ]);
        nextState.emptySpaceI = nextSpaceI;
        nextState.emptySpaceJ = nextSpaceJ;
        nextState.parent = &currentState;
        nextState.lastMove = dir[i];

        nextStates.push_back(nextState);
    }

    return nextStates;
}

// verifica daca o stare anume este o stare finala (puzzle rezolvat)
bool isFinalState(State &state)
{
    int index = 1;
    int dim = state.mat.size();
    for(int i = 0; i < dim; i++)
        for(int j = 0; j < dim; j++)
        {
            if(i == dim - 1 && j == dim - 1)
                continue;

            if(state.mat[i][j] != index)
                return false;

            index++;
        }

    return true;
}

// returneaza directia complementara (pentru sus -> jos; pentru stanga -> dreapta)
Direction complementaryDirection(Direction d)
{
    if(d == Left)
        return Right;
    if(d == Right)
        return Left;
    if(d == Up)
        return Down;
    if(d == Down)
        return Up;
    return None;
}

// functie care rezolva puzzle-ul; returneaza un vector cu
// directiile in care trebuie mutat vectorul
vector<Direction> solvePuzzle(State &initialState)
{
    initialState.lastMove = None;
    initialState.parent = NULL;         // nu are nici un parinte => NULL

    vector<vector<State>> tree;

    // adaugam in arborele de cautare radacina (nodul cu starea initiala)
    tree.push_back({initialState});

    bool solved = false;
    State solution;
    // level = nivelul in arbore pe care cautam
    for(int level = 1; !solved; level++)
    {
        // adaugam un vector gol pentru nivelul actual
        // (nivelul actual nu contine nici o stare, urmeaza sa adaugam)
        tree.push_back({});

        // pentru fiecare stare de pe nivelul anterior generam si adaugam
        // la nivelul actual toate mutarile posibile
        for(int i = 0; i < tree[level - 1].size(); i++)
        {

            // generam mutarile urmatoare pentru o stare de pe nivelul anterior
            vector<State> genereratedStates = generateNextStates(tree[level-1][i]);
            for(int j = 0; j < genereratedStates.size(); j++)
            {
                // daca directia starii actuale este complementara cu ultima directie in care am fost (se anuleaza)
                // atunci nu lua starea in considerare (ea deja exista)
                if(genereratedStates[j].lastMove == complementaryDirection(tree[level-1][i].lastMove))
                {
                    continue;
                }

                // adaugam pe nivelul actual starea genereratedStates[i] (starea actuala generata)
                tree[level].push_back(genereratedStates[j]);

                // am gasit solutia
                if(isFinalState(genereratedStates[j]))
                {
                    solved = true;
                    solution = genereratedStates[j];
                }
            }
        }

        cout << "Done level " << level << "; " << tree[level].size() << " moves" << endl;
    }


    // construim solutia
    vector<Direction> solutionSteps;
    vector<State> solutionStates;
    State *current = &solution;

    while(current != NULL)
    {
        // *var => varibila trebuie sa fie pointer; face din pointer catre tip de data direct tipul de data
        // &var => varibila trebuie sa fie tip de data; face din tipul de data pointer catre tipul de data
        State currentState = *current;
        solutionSteps.push_back(currentState.lastMove);
        solutionStates.push_back(currentState);
        current = currentState.parent;
    }


    // inversez solutionSteps si SolutionStates
    for(int st = 0, dr = solutionSteps.size() - 1; st < dr; st++, dr--)
    {
        swap(solutionSteps[st], solutionSteps[dr]);
        swap(solutionStates[st], solutionStates[dr]);
    }

    // cout << "Steps: \n";
    // for(int i = 0; i < solutionStates.size(); i++)
    // {
    //     printState(solutionStates[i]);
    //     cout << endl;
    // }

    return solutionSteps;
}

bool isSolvable(State &s)
{
    vector<int> v;
    int dim = s.mat.size();
    for(int i = 0; i < dim; i++)
        for(int j = 0; j < 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(dim % 2 == 1)
    {
        return nrInversiuni % 2 == 0;
    }

    int linieSpatiu;
    bool gasit = false;
    int linieSpatiuDeJos = 1;
    for(int i = dim - 1; i >= 0 && !gasit; i--)
    {
        for(int j = 0; j < 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;

}

State readState(const char fileName[])
{
    State s;
    ifstream fin(fileName);
    int n;
    fin >> n;
    s.Resize(n);
    for(int i = 0; i < n; i++)
        for(int j = 0; j < n; j++)
        {
            fin >> s.mat[i][j];
            if(s.mat[i][j] == 0)
            {
                s.emptySpaceI = i;
                s.emptySpaceJ = j;
            }
        }
    fin.close();
    return s;
}

void printStateInFile(const char fileName[], State &s)
{
    ofstream fout(fileName);
    for(int i = 0; i < s.mat.size(); i++)
    {
        for(int j = 0; j < s.mat.size(); j++)
            fout << s.mat[i][j] << ' ';
        fout << '\n';
    }
    fout.close();
}

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

int main()
{
    State initialState = readState("date.in");

    if(!isSolvable(initialState))
    {
        cout << "Cannot sove\n";
        return 0;
    }

    vector<Direction> solutionMoves = solvePuzzle(initialState);
    cout << "Moves to solve the puzzle: \n";
    for(int i = 0; i < solutionMoves.size(); i++)
    {
        if(solutionMoves[i] == Left)
            cout << "Left\n";

        if(solutionMoves[i] == Right)
            cout << "Right\n";

        if(solutionMoves[i] == Up)
            cout << "Up\n";

        if(solutionMoves[i] == Down)
            cout << "Down\n";
    }


    return 0;
}