題目描述：
八方塊移動(dòng)游戲要求從一個(gè)含8個(gè)數(shù)字（用1-8表示）的方塊以及一個(gè)空格方塊（用0表示）的3x3矩陣的起始狀態(tài)開始，不斷移動(dòng)該空格方塊以使其和相鄰的方塊互換，直至達(dá)到所定義的目標(biāo)狀態(tài)?？崭穹綁K在中間位置時(shí)有上、下、左、右4個(gè)方向可移動(dòng)，在四個(gè)角落上有2個(gè)方向可移動(dòng)，在其他位置上有3個(gè)方向可移動(dòng)。例如，假設(shè)一個(gè)3x3矩陣的初始狀態(tài)為：
8 0 3
2 1 4
7 6 5
目標(biāo)狀態(tài)為：
1 2 3
8 0 4
7 6 5
則一個(gè)合法的移動(dòng)路徑為：
8 0 3 8 1 3 8 1 3 0 1 3 1 0 3 1 2 3
2 1 4 => 2 0 4 => 0 2 4 => 8 2 4 => 8 2 4 => 8 0 4
7 6 5 7 6 5 7 6 5 7 6 5 7 6 5 7 6 5
另外，在所有可能的從初始狀態(tài)到目標(biāo)狀態(tài)的移動(dòng)路徑中，步數(shù)最少的路徑被稱為最短路徑；在上面的例子中，最短路徑為5。如果不存在從初試狀態(tài)到目標(biāo)狀態(tài)的任何路徑，則稱該組狀態(tài)無解。
請(qǐng)?jiān)O(shè)計(jì)有效的（細(xì)節(jié)請(qǐng)見評(píng)分規(guī)則）算法找到從八方塊的某初試狀態(tài)到某目標(biāo)狀態(tài)的所有可能路徑中的最短路徑，并用C/C++實(shí)現(xiàn)。
輸入數(shù)據(jù)：
程序需讀入已被命名為start.txt的初始狀態(tài)和已被命名為goal.txt的目標(biāo)狀態(tài)，這兩個(gè)文件都由9個(gè)數(shù)字組成（0表示空格，1-8表示8個(gè)數(shù)字方塊），每行3個(gè)數(shù)字，數(shù)字之間用空格隔開。
輸出數(shù)據(jù)：
如果輸入數(shù)據(jù)有解，輸出一個(gè)表示最短路徑的非負(fù)的整數(shù)；如果輸入數(shù)據(jù)無解，輸出-1。
自測(cè)用例：
如果輸入為：
start.txt和
goal.txt，則產(chǎn)生的輸出應(yīng)為：
5
又例，如果用
7 8 4
3 5 6
1 0 2
替換start.txt中的內(nèi)容，則產(chǎn)生的輸出應(yīng)為：
21
評(píng)分規(guī)則：
1）我們將首先使用和自測(cè)用例不同的10個(gè)start.txt以及相同的goal.txt，每個(gè)測(cè)試用例的運(yùn)行時(shí)間在一臺(tái)Intel Xeon 2.80GHz 4 CPU/6G 內(nèi)存的Linux機(jī)器上應(yīng)不超過10秒（內(nèi)存使用不限制），否則該用例不得分；
2）每個(gè)選手的總分（精確到小數(shù)點(diǎn)后6位）=10秒鐘內(nèi)能產(chǎn)生正確結(jié)果的測(cè)試用例數(shù)量x10+（1/產(chǎn)生這些正確結(jié)果的測(cè)試用例的平均運(yùn)行毫秒)；
3）如果按此評(píng)分統(tǒng)計(jì)仍不能得出總決賽將決出的一、二、三等獎(jiǎng)共計(jì)九名獲獎(jiǎng)?wù)?，我們將先設(shè)N=2，然后重復(fù)下述過程直至產(chǎn)生最高的9位得分：用隨機(jī)生成的另外10個(gè)有解的start.txt再做測(cè)試，并對(duì)這10*N個(gè)測(cè)試用例用2）中公式重新計(jì)算總分，N++。
//冠軍ACRush的代碼：
//轉(zhuǎn)載自：http://star.baidu.com/data/demo/ACRush.txt
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
const int hashsize=70001;
const int maxnode=50000;
const int maxp=40;
const int ten[]=
{1,10,100,1000,10000,100000,1000000,10000000,100000000};
const int C[]={2,3,2,3,4,3,2,3,2};
const int EP[][4]={{1,3,0,0},{0,2,4,0},{1,5,0,0},{0,4,6,0},{1,3,5,7},{2,4,8,0},{3,7,0,0},{4,6,8,0},{5,7,0,0}};
struct Tlist
{
int data,d;
Tlist *next;
};
struct Thashpoint
{
int data;
Thashpoint *next;
};
//Memory
int ID;
Tlist listM[maxnode],*q;
Thashpoint hashM[maxnode],*p;
//data
int src,dest;
//heap
Tlist *head[maxp],*expand[maxp],*lp1,*lp2;
//Hash
Thashpoint *hash[hashsize];
//expand
int nowp,A[9],arcT[9],dist[9][9],b,depth,swap[9][9];
int data,G,newdata,newG;
bool find_answer;
void readdata(const char *filename,int &data)
{
int i,v;
FILE *f=fopen(filename,"r");
data=0;
for (i=0;i<9;i++)
{
fscanf(f,"%d",&v);
data=data+v*ten[i];
}
fclose(f);
}
bool check_noanswer()
{
int p[9],i,b1,b2;
bool vis[9];
for (i=0;i<9;i++)
p[i]=arcT[src/ten[i]%10];
for (b1=0; src/ten[b1]%10!=0;b1++);
for (b2=0;dest/ten[b2]%10!=0;b2++);
int countP=0;
memset(vis,false,sizeof(vis));
for (i=0;i<9;i++)
if (!vis[i])
{
countP++;
for (int k=i;!vis[k];k=p[k])
vis[k]=true;
}
return (countP-dist[b1][b2])%2==0;
}
void preprocess()
{
ID=0;
find_answer=false;
memset(hash,0,sizeof(hash));
memset(head,0,sizeof(head));
memset(expand,0,sizeof(expand));
for (int k=0;k<9;k++)
arcT[dest/ten[k]%10]=k;
for (int u=0;u<9;u++)
for (int v=0;v<9;v++)
{
dist[u][v]=abs(u/3-v/3)+abs(u%3-v%3);
swap[u][v]=ten[u]-ten[v];
}
}
void addnode()
{
if (newdata==dest)
{
printf("%d\n",depth);
find_answer=true;
return;
}
int address=newdata%hashsize;
for (p=hash[address];p!=NULL;p=p->next)
if (p->data==newdata)
return;
if (ID==maxnode)
return;
p=&hashM[ID];
p->data=newdata;
p->next=hash[address];
hash[address]=p;
q=&listM[ID];
ID++;
q->data=newdata;
q->d=depth;
if (newG>=maxp)
return;
if (newG==nowp)
{
q->next=expand[depth];
expand[depth]=q;
}
else
{
q->next=head[newG];
head[newG]=q;
}
}
void solve()
{
nowp=-1;
newdata=src;
newG=0;
for (int k=0;k<9;k++)
if (src/ten[k]%10!=0)
newG+=dist[arcT[src/ten[k]%10]][k];
depth=0;
addnode();
if (find_answer)
return;
for (int p=0;p<maxp;p++) if (head[p]!=NULL)
{
nowp=p;
for (lp1=head[p];lp1!=NULL;lp1=lp2)
{
lp2=lp1->next;
lp1->next=expand[lp1->d];
expand[lp1->d]=lp1;
}
for (int d=0;d<=p;d++)
for (;expand[d]!=NULL;)
{
data=expand[d]->data;
G=p-expand[d]->d;
depth=expand[d]->d+1;
expand[d]->d=-2;
expand[d]=expand[d]->next;
for (b=0;data/ten[b]%10!=0;b++);
for (int v=0;v<C[b];v++)
{
int u=EP[b][v];
int c=data/ten[u]%10;
newdata=data+swap[b][u]*c;
c=arcT[c];
newG=depth+G-dist[c][u]+dist[c][b];
addnode();
if (find_answer)
return;
}
}
}
printf("-1\n");
}
int main()
{
readdata("start.txt",src);
readdata("goal.txt",dest);
preprocess();
if (check_noanswer())
printf("-1\n");
else
solve();
return 0;
}