#include <algorithm>
#include <cmath>
#include <chrono>
#include <cstdlib>
#include <fstream>
#include <iostream>
#include <stdlib.h>
#include <vector>
using namespace std;

template<typename A, typename B> ostream& operator<<(ostream& os, const pair<A, B>& p) { return os << '(' << p.first << ", " << p.second << ')'; }
template < typename T_container, typename T = typename enable_if < !is_same<T_container, string>::value, typename T_container::value_type >::type > ostream& operator<<(ostream& os, const T_container& v) { os << '{'; string sep; for (const T& x : v) os << sep << x, sep = ", "; return os << '}'; }

void dbg_out() { cerr << endl; }
template<typename Head, typename... Tail> void dbg_out(Head H, Tail... T) { cerr << ' ' << H; dbg_out(T...); }
#ifdef NEAL_DEBUG
#define dbg(...) cerr << "(" << #__VA_ARGS__ << "):", dbg_out(__VA_ARGS__)
#else
#define dbg(...)
#endif

struct Node
{
    vector<vector<int>> curState;
    int H, G, N;
    string action;
    Node* parent;
    Node(vector<vector<int>> X, string Action, int g, int h, int n, Node* Parent)
    {
        this->curState = X;
        this->action = Action;
        this->G = g;
        this->N = n;
        this->H = h;
        this->parent = Parent;
    }
};

int getInversion(vector<int> arr)
{
    int inv_count = 0;
    for (unsigned int i = 0; i < arr.size() - 1; ++i)
    {
        for (unsigned int j = i + 1; j < arr.size(); ++j)
        {
            inv_count += ((arr[i] > arr[j]) ? 1 : 0);
        }
    }
    return inv_count;
}

bool isSolvable(vector<vector<int>> curState, int N)
{
    int empty_row = -1;
    vector<int> arr;
    for (int i = 0; i < N; ++i)
    {
        for (int j = 0; j < N; ++j)
        {
            if (curState[i][j])
                arr.push_back(curState[i][j]);
            else empty_row = i;
        }
    }
    int inversions = getInversion(arr);
    if (N % 2 == 0 && (empty_row % 2 == !(inversions % 2)))
        return true;
    if (N % 2 == 1 && inversions % 2 == 0)
        return true;
    return false;
}

void printData(vector<vector<int>> curState, string outputFilePath)
{
    int N = curState.size();
    ofstream fout(outputFilePath, ios::out | ios::app);
    for (int i = 0; i < N; ++i)
    {
        for (int j = 0; j < N; ++j)
        {
            fout << curState[i][j] << " ";
        }
        fout << endl;
    }
    fout << endl;
    fout.close();
}

void getEmptyPosition(vector<vector<int>> curState, int& xPoz, int& yPoz)
{
    for (unsigned int i = 0; i < curState.size(); ++i)
    {
        for (unsigned int j = 0; j < curState.size(); ++j)
        {
            if (curState[i][j] == 0)
            {
                xPoz = i, yPoz = j;
                return;
            }
        }
    }
}

bool canMoveUp(vector<vector<int>> curState, int N, int xPoz, int yPoz)
{
    for (int i = 0; i < N; ++i)
    {
        if (curState[xPoz][yPoz] == curState[0][i])
            return false;
    }
    return true;
}


bool canMoveDown(vector<vector<int>> curState, int N, int xPoz, int yPoz)
{
    for (int i = 0; i < N; ++i)
    {
        if (curState[xPoz][yPoz] == curState[N - 1][i])
            return false;
    }
    return true;
}


bool canMoveLeft(vector<vector<int>> curState, int N, int xPoz, int yPoz)
{
    for (int i = 0; i < N; ++i)
    {
        if (curState[xPoz][yPoz] == curState[i][0])
            return false;
    }
    return true;
}


bool canMoveRight(vector<vector<int>> curState, int N, int xPoz, int yPoz)
{
    for (int i = 0; i < N; ++i)
    {
        if (curState[xPoz][yPoz] == curState[i][N - 1])
            return false;
    }
    return true;
}

void expandState(vector<vector<int>> curState, int N, vector<vector<int>>& child1, vector<vector<int>>& child2, vector<vector<int>>& child3, vector<vector<int>>& child4)
{
    int xPoz, yPoz;
    getEmptyPosition(curState, xPoz, yPoz);
    if (canMoveUp(curState, N, xPoz, yPoz))
    {
        child1 = curState;
        swap(child1[xPoz - 1][yPoz], child1[xPoz][yPoz]);

    }
    if (canMoveDown(curState, N, xPoz, yPoz))
    {
        child2 = curState;
        swap(child2[xPoz + 1][yPoz], child2[xPoz][yPoz]);
    }
    if (canMoveLeft(curState, N, xPoz, yPoz))
    {
        child3 = curState;
        swap(child3[xPoz][yPoz - 1], child3[xPoz][yPoz]);
    }
    if (canMoveRight(curState, N, xPoz, yPoz))
    {
        child4 = curState;
        swap(child4[xPoz][yPoz + 1], child4[xPoz][yPoz]);
    }
}

int getManhattanDistance(vector<vector<int>>curState, vector<vector<int>> goalState, int N)
{
    int manhattan = 0;
    for (int i = 0; i < N; ++i)
    {
        for (int j = 0; j < N; ++j)
        {
            if (i == N - 1 && j == N - 1)
            {
                break;
            }
            for (int x = 0; x < N; ++x)
            {
                for (int y = 0; y < N; ++y)
                {
                    if (goalState[i][j] == curState[x][y])
                        manhattan = manhattan + abs(i - x) + abs(j - y);
                }
            }
        }
    }
    return manhattan;
}

void getChilds(Node curState, int N, vector<Node>& Tree, string outputFilePath, vector<vector<int>> goalState)
{
    vector<vector<int>> child1, child2, child3, child4;
    expandState(curState.curState, N, child1, child2, child3, child4);
    int H;
    if (!child1.empty())
    {
        H = getManhattanDistance(child1, goalState, N);
        Tree.push_back(Node(child1, "UP", curState.G + 1, H, N, &curState));
    }
    if (!child2.empty())
    {
        H = getManhattanDistance(child2, goalState, N);
        Tree.push_back(Node(child2, "DOWN", curState.G + 1, H, N, &curState));
    }
    if (!child3.empty())
    {
        H = getManhattanDistance(child3, goalState, N);
        Tree.push_back(Node(child3, "LEFT", curState.G + 1, H, N, &curState));
    }
    if (!child4.empty())
    {
        H = getManhattanDistance(child4, goalState, N);
        Tree.push_back(Node(child4, "RIGHT", curState.G + 1, H, N, &curState));
    }
}

bool checkForDuplicate(Node node, vector<Node> List)
{
    for (auto itr = List.begin(); itr < List.end(); ++itr)
    {
        if (node.curState == itr->curState)
            return true;
    }
    return false;
}

bool cmp(Node A, Node B)
{
    return A.H + A.G <= B.H + B.G;
}

void aStar(Node input, vector<vector<int>> goalState, int N, string outputFilePath)
{
    vector<Node> openList, closedList;
    openList.push_back(input);
    while (!openList.empty())
    {
        auto min = min_element(openList.begin(), openList.end(), cmp);
        Node curNode = *min;
        if (curNode.curState == goalState || curNode.H == 0)
        {
            cout << curNode.G << endl;
            printData(curNode.curState, outputFilePath);
            // while (curNode.parent != nullptr)
            // {
            //  printData(curNode.parent->curState, outputFilePath);
            //  curNode = *(curNode.parent);
            // }
            /*
                ^
                |
                asta nu functioneaza, n-am stiut cum sa revin la parinti
            */
            return;
        }
        openList.erase(min);
        closedList.push_back(curNode);
        vector<Node> Tree;
        getChilds(curNode, N, Tree, outputFilePath, goalState);
        for (unsigned int i = 0; i < Tree.size(); ++i)
        {
            if (checkForDuplicate(Tree[i], closedList))
                continue;
            if (!checkForDuplicate(Tree[i], openList))
            {
                openList.push_back(Tree[i]);
            }
        }
    }
}

bool checkCorrectData(vector<vector<int>> mat)
{
    vector<int> freq(mat.size() * mat.size(), 0);
    for (unsigned int i = 0; i < mat.size(); ++i)
    {
        for (unsigned int j = 0; j < mat.size(); ++j)
        {
            freq[mat[i][j]]++;
        }
    }
    for (unsigned int i = 0; i < mat.size() * mat.size(); ++i)
    {
        if (freq[i] != 1)
            return true;
    }
    return false;
}

Node readData(string filePath, int& N, vector<vector<int>>& goalState)
{
    vector<vector<int>> givenState;
    cout << "Care este calea fisierului de intrare: ";
    cin >> filePath;
    ifstream fin;
    fin.open(filePath, ios::in);
    if (!fin)
    {
        cerr << "Eroare la deschiderea fisierului " << filePath;
        exit(EXIT_FAILURE);
    }
    fin >> N;
    if (N <= 1)
    {
        cerr << "Dimensiunea puzzle-ului trebuie sa fie minim 2!";
        exit(EXIT_FAILURE);
    }
    vector<vector<int>> X(N, vector<int>(N));
    goalState.resize(N, vector<int>(N));
    for (int i = 0; i < N; ++i)
    {
        for (int j = 0; j < N; ++j)
        {
            fin >> X[i][j];
            if (X[i][j] < 0 || X[i][j] >= (N * N))
            {
                cerr << "Elementele introduse au fost invalide. Introduceti doar valori intre 0 si " << N * N - 1;
                exit(EXIT_FAILURE);
            }
            goalState[i][j] = (N * i + j + 1) % (N * N);
        }
    }
    if (checkCorrectData(X))
    {
        cerr << "Elementele introduse au fost invalide. Introduceti doar valori intre 0 si " << N * N - 1;
        exit(EXIT_FAILURE);
    }
    Node input(X, "None", 0, 0, N, nullptr);
    int H = getManhattanDistance(input.curState, goalState, N);
    input.H = H;
    fin.close();
    return input;
}


int main()
{
    int N;
    string inputFilePath, outputFilePath;
    vector<vector<int>> goalState;
    Node input = readData(inputFilePath, N, goalState);
    cout << "Care este calea fisierului de iesire: "; cin >> outputFilePath;
    if (isSolvable(input.curState, N))
    {
        aStar(input, goalState, N, outputFilePath);
        return 0;
    }
    else
    {
        cerr << "Puzzle-ul introdus nu este rezolvabil!";
        exit(EXIT_FAILURE);
    }
}