#include?
#include?
#include?
#include?“fstream“
#include?“iostream“
#include?“iomanip“
using?namespace?std;

#define?N?9?
ifstream?input（“input.txt“）;
ofstream?output（“ouput.txt“）;
typedef?struct?
{
	char?pa[10];
	char?road[100];
}?ENode;
ENode?st;//開始狀態
ENode?f;//終止狀態
ENode?open[400000];//路徑
bool?closed[1000000000]={0};//保存已經走過的狀態
int?head=0tail=1len=400000;
long?snum=1;

//函數聲明
int?canmove（ENode?*uint?rint?cint?iint?n）;
void?count（int?*int?*ENode?）;
int?empty（void）;
void?init（void）;
void?putintoclose（ENode）;
int?isaim（ENode）;
void?putintoopen（ENode）;
ENode?seach（int?*）;
ENode?takeof（void）;
int?used（ENode?）;
void?print（ENode?mint?t）;
void?move（ENode?*uint?int?char?ch）;
long?change（char?s[]）;


void?main（）
{
	ENode?m;
	int?t;
	init（）;???//初始化
	m=seach（&t）;??//搜索
	print（mt）;???//輸出路徑
	printf（“\n用closed長：%ld\n“snum）;
}
void?init（void）???//
{
	int?i;
	long?u;
	int?c;
	//從文件讀入每個狀態
	for（i=0;i	{
		input>>c;
		st.pa[i]=c+48;
	}
	printf（“初始狀態%s\n“st.pa）;
	strcpy（f.pa“123804765“）;
	for（i=0;i<100;i++）
	{
	f.road[i]=‘\0‘;
	st.road[i]=‘\0‘;
	}
	open[0]=st;
	u=change（st.pa）;
	closed[u]=1;?????//
}

//將每個狀態轉換成一個整數，記錄每個狀態，方便判重
long?change（char?s[]）
{
	int?i;
	long?m=0;
	for（i=0;i<9;i++）
	{
		if（s[i]==‘0‘）
			m=m*10;
		else
			m=m*10+（s[i]-‘0‘）;
	}
	return?m;
}


ENode?seach（int?*t）???//
{
	ENode?m[4];
	int?r;//空格所在的行
	int?c;//空格所在的列
	int?inum=0;

	//如果隊列不空
	while（!empty（））
	{
		m[0]=m[1]=m[2]=m[3]=takeof（）;
		num=strlen（m[0].road）;//該節點已移動的次數
		*t=num+1;????//下一步
		count（&r&cm[0]）;??//計算空位的位置
	????for（i=0;i<4;i++）????//四個方向移動
		{
			if（canmove（&m[i]rcinum））???//判斷是否能移動到該方向
			{
				if（isaim（m[i]））???//如果是最終狀態，則返回
					return?m[i];
				if（!used（m[i]））??//判重
				{
					putintoopen（m[i]）;???//放入隊列
					putintoclose（m[i]）;??//設置是否走過的標志
				}
			}
		}
	}
	return?m[0];
}

//判斷隊列是否為空
int?empty（void）????
{
	if（head==tail）
	{
		printf（“?？?，無解“）;
		printf（“\nPress?any?key?to?continue“）;
		exit（0）;
	}
	return?0;
}

//獲取隊首元素
ENode?takeof（void）??
{
	ENode?t;
	t=open[head++];
	head=head%len;
	return?t;
}

//計算空格所在位置
void?count（int?*rint?*cENode?u）???//
{
	int?i;
	for（i=0;i<10;i++）
		if（u.pa[i]==‘0‘）
		{
			*r=i/3;*c=i%3;
			break;
		}
}

//判斷是否可以擴展
int?canmove（ENode?*uint?r