#include <iostream>
#include <fstream>
using namespace std;

int disparity(int (*targetboard)[4],int (*newboard)[4])
{
	int value(0);
	for(int i=1;i<=3;i++)
	{
		for(int j=1;j<=3;j++)
		{
			if(targetboard[i][j]!=newboard[i][j])
				++value;
		}
	}
	return value;

}
void initboard(int  (*board)[4])
{
	board[1][1]=2;
	board[1][2]=8;
	board[1][3]=3;
	board[2][1]=1;
	board[2][2]=6;
	board[2][3]=4;
	board[3][1]=7;
	board[3][2]=0;
	board[3][3]=5;

}
void copy(int (*board)[4],int (*newboard)[4])
{
	for(int i=1;i<=3;i++)
	{
		for(int j=1;j<=3;j++)
		{
			newboard[i][j]=board[i][j];
		}
	}
}
void print(ofstream & out,int (*board)[4])
{
	
	for(int i=1;i<=3;i++)
	{
		for(int j=1;j<=3;j++)
		{
			out<<board[i][j]<<'\t';
		}
		out<<endl;
	}
	out<<endl;
	
}
int main()
{
	int targetboard[4][4];
	int board[4][4];
	int newboard[4][4];
	targetboard[1][1]=1;
	targetboard[1][2]=2;
	targetboard[1][3]=3;
	targetboard[2][3]=4;
	targetboard[3][3]=5;
	targetboard[3][2]=6;
	targetboard[3][1]=7;
	targetboard[2][1]=8;
	targetboard[2][2]=0;
	initboard(board);
	int zeroX=3;
	int zeroY=2;
	int lastX(0);
	int lastY(0);
	

	int disVal(10);
	int disparityValue;
	int type(5);
	ofstream out("out.txt");
	out<<"Initial:"<<endl;
	print(out,board);
	while(disVal>0)
	{
		disVal = 10;
		
		if(zeroX>1)//up
		{
			if(!((lastX==zeroX-1)&&(lastY==zeroY)))
			{
				copy(board,newboard);
				newboard[zeroX][zeroY]=board[zeroX-1][zeroY];
				newboard[zeroX-1][zeroY]=board[zeroX][zeroY];
				disparityValue = disparity(targetboard,newboard);
				if(disparityValue<disVal)
				{
					type=1;//up
					disVal = disparityValue;
				}
			}
		}
		if(zeroX<3)//down
		{
			if(!((lastX==zeroX+1)&&(lastY==zeroY)))
			{
				copy(board,newboard);
				newboard[zeroX][zeroY]=board[zeroX+1][zeroY];
				newboard[zeroX+1][zeroY]=board[zeroX][zeroY];
				disparityValue = disparity(targetboard,newboard);
				if(disparityValue<disVal)
				{
					type=2;//down
					disVal = disparityValue;
				}
			}
		}
		if(zeroY>1)//left
		{
			if(!((lastX==zeroX)&&(lastY==zeroY-1)))
			{
				copy(board,newboard);
				newboard[zeroX][zeroY]=board[zeroX][zeroY-1];
				newboard[zeroX][zeroY-1]=board[zeroX][zeroY];
				disparityValue = disparity(targetboard,newboard);
				if(disparityValue<disVal)
				{
					type=3;//left
					disVal = disparityValue;
				}
			}
		}
		if(zeroY<3)//right
		{
			if(!((lastX==zeroX)&&(lastY==zeroY+1)))
			{
				copy(board,newboard);
				newboard[zeroX][zeroY]=board[zeroX][zeroY+1];
				newboard[zeroX][zeroY+1]=board[zeroX][zeroY];
				disparityValue = disparity(targetboard,newboard);
				if(disparityValue<disVal)
				{
					type=4;//right
					disVal = disparityValue;
				}
			}
		}

		int temp;
		lastX = zeroX;
		lastY = zeroY;
		switch(type)
		{
		case 1:
			temp  = board[zeroX-1][zeroY];
			board[zeroX-1][zeroY]=board[zeroX][zeroY];
			board[zeroX][zeroY]=temp;
			zeroX = zeroX-1;
			break;
		case 2:
			temp  = board[zeroX+1][zeroY];
			board[zeroX+1][zeroY]=board[zeroX][zeroY];
			board[zeroX][zeroY]=temp;
			zeroX = zeroX+1;
			break;
		case 3:
			temp  = board[zeroX][zeroY-1];
			board[zeroX][zeroY-1]=board[zeroX][zeroY];
			board[zeroX][zeroY]=temp;
			zeroY = zeroY-1;
			break;
		case 4:
			temp  = board[zeroX][zeroY+1];
			board[zeroX][zeroY+1]=board[zeroX][zeroY];
			board[zeroX][zeroY]=temp;
			zeroY = zeroY+1;
			break;
		}
		print(out,board);
		
	}
	cout<<disVal<<endl;
	out.close();
	return 0;
}