八数码问题源代码

 

题目描述：

八方块移动游戏要求从一个含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++实现。

 

输入数据：

程序需读入已被命名为start.txt的初始状态和已被命名为goal.txt的目标状态，这两个文件都由9个数字组成（0表示空格，1-8表示8个数字方块），每行3个数字，数字之间用空格隔开。

 

输出数据：

如果输入数据有解，输出一个表示最短路径的非负的整数；如果输入数据无解，输出-1。

 

自测用例：

如果输入为：start.txt和goal.txt，则产生的输出应为：
5

又例，如果用
7 8 4
3 5 6
1 0 2
替换start.txt中的内容，则产生的输出应为：
21

 

评分规则：

1）我们将首先使用和自测用例不同的10个start.txt以及相同的goal.txt，每个测试用例的运行时间在一台Intel Xeon 2.80GHz 4 CPU/6G 内存的Linux机器上应不超过10秒（内存使用不限制），否则该用例不得分；

2）每个选手的总分（精确到小数点后6位）=10秒钟内能产生正确结果的测试用例数量x10+（1/产生这些正确结果的测试用例的平均运行毫秒)；

3）如果按此评分统计仍不能得出总决赛将决出的一、二、三等奖共计九名获奖者，我们将先设N=2，然后重复下述过程直至产生最高的9位得分：用随机生成的另外10个有解的start.txt再做测试，并对这10*N个测试用例用2）中公式重新计算总分，N++。

//冠军ACRush的代码： 
//转载自：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; 
}