#include <algorithm>
#include <array>
#include <bitset>
#include <cassert>
#include <chrono>
#include <cmath>
#include <cstdlib>
#include <cstring>
#include <fstream>
#include <functional>
#include <iomanip>
#include <iostream>
#include <map>
#include <numeric>
#include <queue>
#include <random>
#include <set>
#include <stdexcept>
#include <stdlib.h>
#include <unordered_map>
#include <unordered_set>
#include <utility>
#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;
    }
    Node& operator = (const Node &b)
    {
        this->H = b.H;
        this->G = b.G;
        this->N = b.N;
        this->action = b.action;
        this->curState = b.curState;
        this->parent = b.parent;
        return *this;
    }
};

//ACTION = 0 -> UP; 1-> DOWN; 2 - > LEFT 3-> RIGHT

int getInversion(vector<int> arr)
{
    int inv_count = 0;
    for (int i = 0; i < arr.size() - 1; ++i)
    {
        for (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 (int i = 0; i < curState.size() ; ++i)
    {
        for (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)
{
    //child1 - up child2 - down child3 - left child4 - right
    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 manhattan_distance(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);
    //dbg(child1, child2, child3, child4);
    int H;
    if (!child1.empty())
    {
        H = manhattan_distance(child1, goalState, N);
        // cout << "Ajung aici?";
        //printData(child1, outputFilePath);
        Tree.push_back(Node(child1, "UP", curState.G + 1, H, N, &curState));
    }
    if (!child2.empty())
    {
        H = manhattan_distance(child2, goalState, N);
        // cout << "Ajung aici?";
        //printData(child2, outputFilePath);
        Tree.push_back(Node(child2, "DOWN", curState.G + 1, H, N, &curState));
    }
    if (!child3.empty())
    {
        H = manhattan_distance(child3, goalState, N);
        // cout << "Ajung aici?";
        //printData(child3, outputFilePath);
        Tree.push_back(Node(child3, "LEFT", curState.G + 1, H, N, &curState));
    }
    if (!child4.empty())
    {
        H = manhattan_distance(child4, goalState, N);
        // cout << "Ajung aici?";
        //printData(child4, outputFilePath);
        Tree.push_back(Node(child4, "RIGHT", curState.G + 1, H, N, &curState));
    }
    //dbg(level);
    // for (auto itr = Tree.begin(); itr != Tree.end(); ++itr) {
    //  cout << itr->curState << "\n";
    // }
}

int findIndex(Node c, vector<Node> list)
{
    for (int i = 0; i < list.size(); ++i)
    {
        if (list[i].curState == c.curState)
        {
            return i;
        }
    }
}

bool checkForDuplicates(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);
    int contor = 0;
    while (!openList.empty())
    {
        contor++;
        dbg(contor);
        auto min = min_element(openList.begin(), openList.end(), cmp);
        Node process = *min;
        if (process.curState == goalState || process.H == 0)
        {
            cout << contor << endl;
            printData(process.curState, outputFilePath);
            // while (process.parent)
            // {
            //  printData(process.parent->curState, outputFilePath);
            //  process = *(process.parent);
            // }
            return;
        }
        openList.erase(min);
        closedList.push_back(process);
        vector<Node> Tree;
        getChilds(process, N, Tree, outputFilePath, goalState);
        cout << Tree.size();
        for (int i = 0; i < Tree.size(); ++i)
        {
            if (!checkForDuplicates(Tree[i], openList))
            {
                openList.push_back(Tree[i]);
            }
            else
            {
                Node curNode = openList[findIndex(Tree[i], openList)];
                if (Tree[i].G < curNode.G)
                {
                    curNode = Tree[i];
                }
            }
        }
    }
}

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;
    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];
            goalState[i][j] = (N * i + j + 1) % (N * N);
        }
    }
    Node input(X, "None", 0, 0, N, nullptr);
    int H = manhattan_distance(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);
    }
    // int N;
    // vector<vector<int>> curState;
    // string inputFilePath, outputFilePath;
    // curState = readData(inputFilePath, N);
    // dbg(curState);
    // if (isSolvable(curState, N))
    // {
    //  cout << "\nCare este calea fisierului de iesire: ";
    //  cin >> outputFilePath;
    //  printData(curState, outputFilePath);
    //  int level = 0;
    //  vector<pair<vector<vector<int>>, int>> Tree;
    //  Tree.push_back(make_pair(curState, level));
    //  dbg(Tree);
    //  getChilds(curState, N, level, Tree, outputFilePath);
    //  if (checkForDuplicates(Tree) == false)
    //  {
    //      cout << "Au fost gasite duplicate";
    //  }
    //  else cout << "Nu exista duplicate";
    //  return 0;
    // }
    // else
    // {
    //  cerr << "Puzzle-ul introdus nu este rezolvabil!";
    //  exit(EXIT_FAILURE);
    // }
}