大家再来看一下上一次的百度之星编程赛的决赛题答案，给一个详细的分析，谢谢！
题目描述如下：
题目描述：八方块移动游戏要求从一个含8个数字（用1-8表示）的方块以及一个空格方块（用0表示）的3x3矩阵的起始状态开始，不断移动该空格方块以使其和相邻的方块互换，直至达到所定义的目标状态。空格方块在中间位置时有上、下、左、右4个方向可移动，在四个角落上有2个方向可移动，在其他位置上有3个方向可移动。例如，假设一个3x3矩阵的初始状态为：
8 0 3
2 1 4
7 6 5
目标状态为：
1 2 3
8 0 4
7 6 5
则一个合法的移动路径为：
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
另外，在所有可能的从初始状态到目标状态的移动路径中，步数最少的路径被称为最短路径；在上面的例子中，最短路径为5。如果不存在从初试状态到目标状态的任何路径，则称该组状态无解。
请设计算法找到从八方块的某初试状态到某目标状态的所有可能路径中的最短路径，并用C/C++实现。
a
输入数据：程序需读入已被命名为start.txt的初始状态和已被命名为goal.txt的目标状态，这两个文件都由9个数字组成（0表示空格，1-8表示8个数字方块），每行3个数字，数字之间用空格隔开。假定start.txt和goal.txt不会相同。
输出数据：如果输入数据有解，输出一个表示最短路径的非负的整数；如果输入数据无解，输出-1。请在数字输出后再输出一回车换行符。
自测用例：如果输入为：start.txt和goal.txt，则产生的输出应为：
5
如果用
7 8 4
3 5 6
1 0 2
替换start.txt中的内容，则产生的输出应为：
21
如果用
7 5 2
0 6 3
4 1 8
替换start.txt中的内容，则产生的输出应为：
-1
评分规则：我们将首先使用10组不同的start.txt和goal.txt进行测试，每个测试用例的运行时间在一台Intel Xeon 2.80GHz 4 CPU/6G 内存的Linux机器上应不超过10秒（内存使用不限制），否则该用例不得分；
答案是冠军楼天城的，代码如下：
#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;
}
总体上用的是A*算法，但是具体行为上不是很懂。。希望得到各位大虾们详尽一些的理解。。只求在算法理解上做一些提点就可以了，万分感谢。。
问题点数：40、回复次数：15Top
1 楼wzh0591（企鹅）回复于 2006-06-03 22:39:04 得分 0
MARK，帮你顶一下，有空时来解！Top
2 楼wxinyuan（冰封）回复于 2006-06-03 22:53:02 得分 0
谁说一下思路，文件操作的不算，就是几个数字的走法的思路Top
3 楼jixingzhong（瞌睡虫·星辰）回复于 2006-06-04 09:30:35 得分 0
有空再来看看 ...Top
4 楼coolnick（林息）回复于 2006-06-04 10:24:51 得分 0
其实就是排序的问题，只是排序移动的方式与常规有点不同而已，
一共就9个位置，每个数字的移动方式都是固定的。
每次移动的依据就是移动后大的数在后面就可以了Top
5 楼End_less（）回复于 2006-06-04 18:27:44 得分 0
继续MARK.....Top
6 楼laiwusheng（风清扬）回复于 2006-06-04 18:52:30 得分 0
关注Top
7 楼diedknight（diedknight）回复于 2006-06-05 10:39:49 得分 0
希望有高人给出注释。。。Top
8 楼jjw97_5（建文）回复于 2006-06-05 15:43:22 得分 0
关注Top
9 楼woundedsoul（MissWolf）回复于 2006-07-11 17:28:34 得分 0
mark一下！有空过来看Top
10 楼FlowingWatering（）回复于 2006-07-11 17:40:35 得分 0
好像是去年的题目——“重排九宫”问题。
具体程序没看，不过推荐用人工智能里“启发式搜索”去做，穷举的话恐怕......Top
11 楼yingge（...木脑壳...）回复于 2006-07-11 17:41:46 得分 0
路过留个名Top
12 楼universes（及时揭帖是一种美德 | CSDN也这么黑）回复于 2006-07-12 14:44:40 得分 0
markTop
13 楼Jim_King_2000（）回复于 2006-07-12 15:27:27 得分 0
看《人工智能》吧。里面有A*算法的详细介绍及证明。Top
14 楼Sherwin（争做结帖第一人）回复于 2006-07-12 17:44:59 得分 0
人工智能没学过,不会.为了练练好久没有用的脑子,用java采用穷举法做了一下.
用上面那个21步的例子,程序跑了2秒多.Top
15 楼Jim_King_2000（）回复于 2006-07-12 23:43:33 得分 0
楼上的，无论什么语言，能写出来已经很不容易了,顶一下。用的是深度优先还是广度优先？Top
