#include<iostream>
#include<map>
#include<vector>
using namespace std ;
struct closed_struct
{
int num ;
int a[3][3] ;
int parent ;
char dirt ;
} closed[10000000] ;
int cont ;
multimap< int , closed_struct> open ; // 队列
vector< int > stack ;
typedef vector< int > ::iterator v_iter ;
int ans[3][3] ={ 1 , 2 , 3
, 8 , 0 , 4
, 7 , 6 , 5 } ;
bool compare( int p[][3] , int t[][3] )
{
for( int i = 0 ; i < 3 ; ++ i )
for( int j = 0 ; j < 3 ; ++ j )
if( p[i][j] != t[i][j] ) return false ;
return true ;
}
void pout( int p[][3] )
{
for( int i = 0 ; i < 3 ; ++ i )
{
for( int j = 0 ; j < 3 ; ++ j )
cout << p[i][j] << " ";
cout << endl;
}
cout << endl ;
}
void swap( int & i , int & j )
{
i = i ^ j ;
j = i ^ j ;
i = i ^ j ;
}
//************************估值函数*******************************
int h( int p[][3] )
{
int temp = 0 ;
for( int i = 0 ; i < 3 ; ++ i )
for( int j = 0 ; j < 3 ; ++ j )
if( p[i][j] != ans[i][j] ) temp ++ ;
return temp ;
}
//***************************************************************
int bps()
{
closed_struct temp , son ;
bool flag = false ;
while( !open.empty() )
{
int cost = open.begin()->first ;
temp = open.begin()->second ;
open.erase(open.begin()) ;
cout << cost << endl ;
if( compare( temp.a , ans ) ) return temp.num ;
int ii , jj ;
for( int i = 0 ; i < 3 ; ++ i )
for( int j = 0 ; j < 3 ; ++ j )
if( temp.a[i][j] == 0 ) { ii = i ; jj = j ; }
bool flag = false ;
if( temp.dirt != 'y' )
{
son = temp ;
if( jj != 0 )
{
swap( son.a[ii][jj] , son.a[ii][jj-1] ) ;
for( int i = 0 ; i < cont ; ++ i )
if( compare( son.a , closed[i].a) ) {
flag = true ; break ; }
if( !flag )
{
son.parent = temp.num ;
son.num = cont ;
son.dirt = 'z' ;
closed[cont++] = son ;
int cost_now = cost + 1 + h(son.a);
open.insert(make_pair( cost_now , son) ) ;
}
}
}
if( temp.dirt != 'x' )
{
son = temp ;
if( ii != 0 )
{
swap( son.a[ii][jj] , son.a[ii-1][jj] ) ;
flag = false ;
for( int i = 0 ; i < cont ; ++ i )
if( compare( son.a , closed[i].a) ) { flag = true ; break ; }
if( !flag )
{
son.parent = temp.num ;
son.num = cont ;
son.dirt = 's' ;
closed[cont++] = son ;
int cost_now = cost + 1 + h(son.a);
open.insert(make_pair( cost_now , son) ) ;
}
}
}
if( temp.dirt != 'z' )
{
son = temp ;
if( jj != 2 )
{
swap( son.a[ii][jj] , son.a[ii][jj+1] ) ;
flag = false ;
for( int i = 0 ; i < cont ; ++ i )
if( compare( son.a , closed[i].a) ) { flag = true ; break ; }
if( !flag )
{
son.parent = temp.num ;
son.num = cont ;
son.dirt = 'y' ;
closed[cont++] = son ;
int cost_now = cost + 1 + h(son.a);
open.insert(make_pair( cost_now , son) ) ;
}
}
}
if( temp.dirt != 's' )
{
son = temp ;
if( ii != 2 )
{
swap( son.a[ii][jj] , son.a[ii+1][jj] ) ;
flag = false ;
for( int i = 0 ; i < cont ; ++ i )
if( compare( son.a , closed[i].a) ) { flag = true ; break ; }
if( !flag )
{
son.parent = temp.num ;
son.num = cont ;
son.dirt = 'x' ;
closed[cont++] = son ;
int cost_now = cost + 1 + h(son.a);
open.insert(make_pair( cost_now , son) ) ;
}
}
}
}
return -1 ;
}
void path_back( int now )
{
stack.clear() ;
int temp = now ;
stack.push_back( temp ) ;
while( temp != 0 )
{
temp = closed[temp].parent ;
stack.push_back( temp ) ;
}
cout << "pathback" << endl;
while( !stack.empty() )
{
pout( closed[stack.back()].a ) ;
stack.pop_back() ;
}
cout << "pathback over" << endl;
}
int main()
{
closed_struct temp ;
for( int i = 0 ; i < 3 ; ++ i )
for( int j = 0 ; j < 3 ; ++ j )
cin >> temp.a[i][j] ;
temp.parent = 0 ;
temp.dirt = 0 ;
temp.num = 0 ;
closed[cont] = temp ;
cont ++ ;
cout << h(temp.a) << endl;
open.insert( make_pair( h(temp.a) , temp ) ) ;
int now = bps() ;
cout << "bps结束" << endl;
if( now == -1 ) cout << "error" << endl ;
else path_back( now ) ;
system("pause") ;
}