#include <iostream>
#include <stack>
#include <limits>
#include <queue>
#include <climits>
using namespace std;
// solutia finala urmarita
char goal[3][3] = {{'1','2','3'},{'8', ' ','4'},{'7','6','5'}} ;
struct treenode
{
    char b[3][3] ;
    int value; // the key
    struct treenode *left, *right;
    int level;
} *treeroot = NULL;
// calculeaza cheia asociata configuratiei curente
int puzzlevalue(char b[3][3])
{
    int k = 1;
    int value = 0;
    for(int i=0; i<3; i++)
        for(int j=0; j<3; j++)
        {
            if (b[i][j] != ' ') value += k*(b[i][j]-'0');
            k *= 10;
        }
    return value;
}
// adauga un nou nod in arbore
int addnode(struct treenode *&t, char b[3][3])
{
    int value = puzzlevalue(b);
    if(t == NULL)
    {
        t = new struct treenode;
        t -> left = t -> right = NULL;
        for(int i=0; i<3; i++)
            for (int j=0; j<3; j++)
                t-> b[i][j] = b[i][j];
        t->value = value;
        return 1;
    }
    if(value < t->value) return addnode(t->left,b);
    if(value > t->value) return addnode(t->right,b);
    return 0;
}
// schimba valorile a doua pozitii
void swap(char &a, char &b)
{
    a^=b;
    b^=a;
    a^=b;
}
// afiseaza configuratia curenta
void print(char b[3][3])
{
    for(int i=0; i<3; i++)
    {
        for(int j=0; j<3; j++) cout << b[i][j] << " ";
        cout << endl;
    }
    cout << endl;
}
// genereaza arborele binar
int btgen(char b[3][3], int x, int y)
{
    int g, k=puzzlevalue(b);
    if(k==567408321)
    {
        addnode(treeroot, b);
        return 1;
    }
    if(x > 0)
    {
        swap(b[x][y], b[x-1][y]);
        if(addnode(treeroot, b)) g = btgen(b,x-1,y);
        else g=0;
        swap(b[x][y],b[x-1][y]);
        if(g) return 1; // daca am gasit nu mai continui
    }
    if(y > 0)
    {
        swap(b[x][y],b[x][y-1]);
        if(addnode(treeroot,b))
            g = btgen(b,x,y-1);
        else
            g=0;
        swap(b[x][y],b[x][y-1]);
        if(g)
            return 1;
    }
    if(x<2)
    {
        swap(b[x] [y],b[x+1] [y] ) ;
        if(addnode(treeroot,b)) g = btgen(b,x+1,y);
        else g=0;
        swap(b[x][y],b[x+1][y]);
        if(g) return 1;
    }
    if(y < 2)
    {
        swap(b[x][y],b[x][y+1]);
        if(addnode(treeroot,b)) g = btgen(b,x,y+1);
        else g=0;
        swap(b[x][y],b[x][y+1]);
        if(g) return 1;
    }
    return 0;
}

int cnt(treenode *treeroot, int level) {
    if (treeroot == NULL) {
        return 0;
    } else {
        treeroot->level = level;
        return cnt(treeroot->left, level + 1) + cnt(treeroot->right, level + 1) + 1;
    }
}


bool search(treenode *root, int value) {
    if (root == NULL) {
        return false;
    } else if (root->value == value) {
        return true;
    } else {
        return search(root->right, value) | search(root->left, value);
    }
}


int minF = INT_MAX;
int maxF = INT_MIN;
int minLevel;
int maxLevel;
int graphLevel;
int solLevel = -1;

void searchMinMaxAndSol(treenode *root) {
    queue<treenode *> q;
    q.push(root);

    while (!q.empty()) {
        treenode *n = q.front();
        q.pop();
        if (n->value > maxF) {
            maxF = n->value;
            maxLevel = n->level;
        }
        if (n->value < minF) {
            minF = n->value;
            minLevel = n->level;
        }

        if(n->value == 567408321) {
            solLevel = n->level;
        }

        if (n->left) {
            q.push(n->left);
        }
        if (n->right) {
            q.push(n->right);
        }

        graphLevel = n->level;
    }
}
// exemplificare
int main(void)
{
    int N;
// configuratia de start
    char b[3][3] = {{'6','1','2'}, {'5','8','7'},{'4','3',' '}};
    if(btgen(b,2,2))
    {
// numarul de noduri
        N=0;
        N = cnt(treeroot, 0);
        cout << "\n" << N << " noduri\n\n";
        if(!search(treeroot, 567408321))
            cout << "NU ";
        cout << "exista solutia!\n\n";
// nivel val maxima, minima
        //int nmax=0, nmin=0;
        searchMinMaxAndSol(treeroot);
        cout << "\ncheia cu val min " << minF << " este pe niv " << minLevel;
        cout << "\ncheia cu val max " << maxF << " este pe niv " << maxLevel;
//        cout << "\ninaltimea arborelui este " << Height(treeroot,0);
        //int H=0;
        //height(treeroot,0);
        cout << "\nsolutia este pe nivelul " << solLevel;
        cout << "\ninaltimea arborelui este " << graphLevel << endl;

    }
    else
        cout << "\nNu a fost identificata solutia " << endl;
    return 0;
}