import java.io.*;
import java.util.*;
public class Eight_figureses{
static int opennumber=0;
static int closenumber=0;
static nodal_point begin_point;
static nodal_point end_point;
static nodal_point[] open_point=new nodal_point[10000];
static nodal_point[] close_point=new nodal_point[10000];
public Eight_figureses(){
}
public void expend(nodal_point point){
nodal_point best=new nodal_point();
int k=-1,g=0;
if(point.enqual(end_point)){
System.out.println("目标已经找到");
this.read(point);
System.out.println("深度为:"+point.hight);
return;
}
else {
System.out.println("------------------------待扩展的节点-----------------");
this.read(point);
point.zero();
System.out.print("空格的位置为:");
if(point.location[0]==0&&point.location[1]==0)
System.out.println("左上角");
else if(point.location[0]==0&&point.location[1]==1)
System.out.println("第一行中间");
else if(point.location[0]==0&&point.location[1]==2)
System.out.println("右上角");
else if(point.location[0]==1&&point.location[1]==0)
System.out.println("第一列中间");
else if(point.location[0]==1&&point.location[1]==1)
System.out.println("正中");
else if(point.location[0]==1&&point.location[1]==2)
System.out.println("第三列中间");
else if(point.location[0]==2&&point.location[1]==0)
System.out.println("左下角");
else if(point.location[0]==2&&point.location[1]==1)
System.out.println("第三行中间");
else if(point.location[0]==2&&point.location[1]==2)
System.out.println("右下角");
point.nosame(point);
System.out.println("扩展节点的深度为:"+point.hight);
System.out.println("扩展节点中的不同点的个数为:"+point.different);
System.out.println("扩展节点的耗散值为:"+(point.hight+point.different));
for(int i=0;i<this.opennumber;i++)
if(open_point[i]==point)
k=i;
if(k!=-1){
for(int i=k;i<this.opennumber-1;i++)
open_point[i]=open_point[i+1];
opennumber--;
close_point[closenumber]=point;
closenumber++;
}
if(point.location[0]==0&&point.location[1]==0)
{
this.zhankai(point,2,0,1,point.location);
this.zhankai(point,3,1,0,point.location);
}
else if(point.location[0]==0&&point.location[1]==1)
{
this.zhankai(point,0,0,0,point.location);
this.zhankai(point,2,0,2,point.location);
this.zhankai(point,3,1,1,point.location);
}
else if(point.location[0]==0&&point.location[1]==2)
{
this.zhankai(point,0,0,1,point.location);
this.zhankai(point,3,1,2,point.location);
}
else if(point.location[0]==1&&point.location[1]==0)
{
this.zhankai(point,1,0,0,point.location);
this.zhankai(point,2,1,1,point.location);
this.zhankai(point,3,2,0,point.location);
}
else if(point.location[0]==1&&point.location[1]==1)
{
this.zhankai(point,0,1,0,point.location);
this.zhankai(point,1,0,1,point.location);
this.zhankai(point,2,1,2,point.location);
this.zhankai(point,3,2,1,point.location);
}
else if(point.location[0]==1&&point.location[1]==2)
{
this.zhankai(point,0,1,1,point.location);
this.zhankai(point,1,0,2,point.location);
this.zhankai(point,3,2,2,point.location);
}
else if(point.location[0]==2&&point.location[1]==0)
{
this.zhankai(point,1,1,0,point.location);
this.zhankai(point,2,2,1,point.location);
}
else if(point.location[0]==2&&point.location[1]==1)
{
this.zhankai(point,0,2,0,point.location);
this.zhankai(point,1,1,1,point.location);
this.zhankai(point,2,2,2,point.location);
}
else if(point.location[0]==2&&point.location[1]==2)
{
this.zhankai(point,0,2,1,point.location);
this.zhankai(point,1,1,2,point.location);
}
best=this.open_point[0];
best.nosame(best);
for(int i=1;i<this.opennumber;i++){
open_point[i].nosame(open_point[i]);
if((best.hight+best.different)>(open_point[i].hight+open_point[i].different))
best=open_point[i];
}
this.expend(best);
}
}
public void zhankai(nodal_point point,int derection,int x,int y,int[] zerolocation){
boolean flag1=true,flag2=true;
nodal_point temp=new nodal_point();
for(int i=0;i<3;i++)
for(int j=0;j<3;j++)
temp.figur[i][j]=point.figur[i][j];
int change;
change=temp.figur[zerolocation[0]][zerolocation[1]];
temp.figur[zerolocation[0]][zerolocation[1]]=temp.figur[x][y];
temp.figur[x][y]=change;
for(int i=0;i<this.opennumber;i++)
if(open_point[i].enqual(temp)){
flag1=false;
break;
}
for(int i=0;i<this.closenumber;i++)
if(close_point[i].enqual(temp)){
flag2=false;
break;
}
if(flag1&&flag2) {
if(derection==0){
System.out.println("向左扩展为:");
this.read(temp);
}
else if(derection==1){
System.out.println("向上扩展为:");
this.read(temp);
}
else if(derection==2){
System.out.println("向右扩展为:");
this.read(temp);
}
else if(derection==3){
System.out.println("向下扩展为:");
this.read(temp);
}
temp.hight=point.hight+1;
open_point[opennumber]=temp;
opennumber++;
}
}
public static void read(nodal_point readpoint){
for(int i=0;i<3;i++){
for(int j=0;j<3;j++)
System.out.print(" "+readpoint.figur[i][j]);
System.out.println();
}
}

public int[] input(){
int[] middle=new int[9];
try{
for(int i=0;i<9;i++){
BufferedReader in=new BufferedReader(new InputStreamReader(System.in));
middle[i]=Integer.parseInt(in.readLine());
}
}
catch(IOException e){}
return middle;
}
public static class nodal_point{
int[] location=new int[2];
int[][] figur=new int[3][3];
int hight=0;
int different=0;
public nodal_point(){}
public nodal_point(int[] data){
int k=0;
for(int i=0;i<3;i++)
for(int j=0;j<3;j++){
figur[i][j]=data[k];
k++;
}
}
public boolean enqual(nodal_point aim){
for(int i=0;i<3;i++)
for(int j=0;j<3;j++)
if(this.figur[i][j]!=aim.figur[i][j])
return false;
return true;
}
public void nosame(nodal_point point){
different=0;
for(int i=0;i<3;i++)
for(int j=0;j<3;j++)
if((end_point.figur[i][j]!=point.figur[i][j])&&end_point.figur[i][j]!=0) this.different++;

}
public void zero(){
for(int i=0;i<3;i++)
for(int j=0;j<3;j++)
if(this.figur[i][j]==0){
this.location[0]=i;
this.location[1]=j;
}
}
}
public static void main(String[] args){
int[] begin=new int[9];
int[] end=new int[9];
Eight_figureses eight=new Eight_figureses();

System.out.println("请输入开始队列:");
begin=eight.input();
System.out.println("请输入目标队列:");
end=eight.input();
eight.begin_point=new nodal_point(begin);
eight.end_point=new nodal_point(end);
eight.open_point[eight.opennumber]=eight.begin_point;
eight.opennumber++;
eight.expend(eight.begin_point);
}
}