#include <iostream>
#include <cmath>
#include <algorithm>
#include <fstream>

using namespace std;

struct Kamen{
    int cislo;
    int poziceX;
    int poziceY;
    int pozadovaneX;
    int pozadovaneY;
    int vzdalenost;
    bool tah;
};

const int m_spravnaMatice [3][3] = { {1,2,3}, {8,0,4}, {7,6,5} };
int matice1[3][3] = { {1,2,3}, {0,8,4}, {7,6,5} }; // pomocna matice pro nacteni hodnot
Kamen m_vstupniMatice[3][3];

void nastaveniFalse(Kamen vstupniMatice[3][3]){
    for(int i = 0; i < 3; i++)
        for(int j = 0; j < 3; j++)
            vstupniMatice[i][j].tah = false;
}

void inicializace(Kamen vstupniMatice[3][3]){

    // nacteni hodnot kamenu v sachovnici (nastaveni parametru cislo)
    for(int i = 0; i < 3; i++)
        for(int j = 0; j < 3; j++)
            vstupniMatice[i][j].cislo = matice1[i][j];

    // aktualni pozice kamenu v sachovnici (nastaveni parametru poziceX a poziceY)
    vstupniMatice[0][0].poziceX = 0;
    vstupniMatice[0][0].poziceY = 0;
    vstupniMatice[0][1].poziceX = 0;
    vstupniMatice[0][1].poziceY = 1;
    vstupniMatice[0][2].poziceX = 0;
    vstupniMatice[0][2].poziceY = 2;
    vstupniMatice[1][0].poziceX = 1;
    vstupniMatice[1][0].poziceY = 0;
    vstupniMatice[1][1].poziceX = 1;
    vstupniMatice[1][1].poziceY = 1;
    vstupniMatice[1][2].poziceX = 1;
    vstupniMatice[1][2].poziceY = 2;
    vstupniMatice[2][0].poziceX = 2;
    vstupniMatice[2][0].poziceY = 0;
    vstupniMatice[2][1].poziceX = 2;
    vstupniMatice[2][1].poziceY = 1;
    vstupniMatice[2][2].poziceX = 2;
    vstupniMatice[2][2].poziceY = 2;

    // pozadovana pozice kamenu v sachovnici (nastaveni parametru pozadovaneX a pozadovaneY)
    vstupniMatice[0][0].pozadovaneX = 0;
    vstupniMatice[0][0].pozadovaneY = 0;
    vstupniMatice[0][1].pozadovaneX = 0;
    vstupniMatice[0][1].pozadovaneY = 1;
    vstupniMatice[0][2].pozadovaneX = 0;
    vstupniMatice[0][2].pozadovaneY = 2;
    vstupniMatice[1][0].pozadovaneX = 1; // [1][0] -> [1][1]
    vstupniMatice[1][0].pozadovaneY = 1; // [1][0] -> [1][1]
    vstupniMatice[1][1].pozadovaneX = 1; // [1][1] -> [1][0]
    vstupniMatice[1][1].pozadovaneY = 0; // [1][1] -> [1][0]
    vstupniMatice[1][2].pozadovaneX = 1;
    vstupniMatice[1][2].pozadovaneY = 2;
    vstupniMatice[2][0].pozadovaneX = 2;
    vstupniMatice[2][0].pozadovaneY = 0;
    vstupniMatice[2][1].pozadovaneX = 2;
    vstupniMatice[2][1].pozadovaneY = 2;
    vstupniMatice[2][2].pozadovaneX = 2;
    vstupniMatice[2][2].pozadovaneY = 1;

    // nastaveni moznosti tahnuti kamenem po sachovnici na false (nastaveni parametru tah)
    nastaveniFalse(m_vstupniMatice);
}

void lzePresunout(Kamen vstupniMatice[3][3]){

    // nasledne nalezeni kamenu,se kterymi lze hybat
    for(int i = 0; i < 3; i++)
        for(int j = 0; j < 3; j++)
            if(((i-1) >= 0) || ((j-1) >= 0) || ((i+1) <= 2) || ((j+1) <= 2))
                if( ((vstupniMatice[i][j-1].cislo == 0) && ((j-1) >= 0)) || ((vstupniMatice[i-1][j].cislo == 0) && ((i-1) >= 0)) ||
                    ((vstupniMatice[i][j+1].cislo == 0) && ((j+1) <= 2)) || ((vstupniMatice[i+1][j].cislo == 0) && ((i+1) <= 2)) )
                        vstupniMatice[i][j].tah = true;
}

int porovnaniMatice(Kamen vstupniMatice[3][3]){
    int i;
    int j;
    int spravne = 0;
    for (i = 0; i < 3; i++)
        for (j = 0; j < 3; j++)
            if(vstupniMatice[i][j].cislo == m_spravnaMatice[i][j])
                spravne ++;
    return spravne;
}

void presunKostku(Kamen vstupniMatice[3][3]){
    int pom1;
    int pom2;
    Kamen pomMatice[3][3] = Kamen vstupniMatice[3][3];
    int pocetSpravnych;
    int novyPocetSpravnych;
    int pocetKroku;
    pocetSpravnych = 0;
    pocetKroku = 0;
    for(int i = 0; i < 3; i++)
        for(int j = 0; j < 3; j++)
            if(vstupniMatice[i][j].cislo == m_spravnaMatice[i][j])
                pocetSpravnych ++;

    while(novyPocetSpravnych != 9 || pocetKroku < 100){
        for(int i = 0; i < 3; i++)
        for(int j = 0; j < 3; j++)
            if(vstupniMatice[i][j].cislo == 0)
            {
                    pom1 = vstupniMatice[i][j].poziceX;
                    pom2 = vstupniMatice[i][j].poziceY;
                    vstupniMatice[i][j].poziceX = vstupniMatice[i][j-1].poziceX;
                    vstupniMatice[i][j].poziceY = vstupniMatice[i][j-1].poziceY;
                    vstupniMatice[i][j-1].poziceX = pom1;
                    vstupniMatice[i][j-1].poziceY = pom2;
                    pocetKroku ++;
                    novyPocetSpravnych = porovnaniMatice(m_vstupniMatice);
                    nastaveniFalse(m_vstupniMatice);
                    lzePresunout(m_vstupniMatice);
            }
                        if(novyPocetSpravnych < pocetSpravnych)
                        {
                            pom1 = vstupniMatice[i][j].poziceX;
                            pom2 = vstupniMatice[i][j].poziceY;
                            vstupniMatice[i][j].poziceX = vstupniMatice[i][j-1].poziceX;
                            vstupniMatice[i][j].poziceY = vstupniMatice[i][j-1].poziceY;
                            vstupniMatice[i][j-1].poziceX = pom1;
                            vstupniMatice[i][j-1].poziceY = pom2;
                            pocetKroku --;
                            nastaveniFalse(m_vstupniMatice);
                            lzePresunout(m_vstupniMatice);
                        }
            }
}

int main(int argc, char *argv[]){

    inicializace(m_vstupniMatice);
    lzePresunout(m_vstupniMatice);
    //presunKostku(m_vstupniMatice);

    /*
    int i = 0;
    for (int j = 0; j < 3; j++)
        cout << m_vstupniMatice[i][j].tah << " " << m_vstupniMatice[i][j].cislo << " ";
        cout << endl;
    i = 1;
    for (int j = 0; j < 3; j++)
        cout << m_vstupniMatice[i][j].tah << " " << m_vstupniMatice[i][j].cislo << " ";
        cout << endl;
    i = 2;
    for (int j = 0; j < 3; j++)
        cout << m_vstupniMatice[i][j].tah << " " << m_vstupniMatice[i][j].cislo << " ";
        cout << endl;
    */

    return 0;
}