1225 八数码难题

 

 时间限制: 1 s

 空间限制: 128000 KB

 题目等级 : 钻石 Diamond

 查看运行结果

 

 

题目描述 

Description

Yours和zero在研究A*启发式算法.拿到一道经典的A*问题,但是他们不会做,请你帮他们.

问题描述

在3×3的棋盘上，摆有八个棋子，每个棋子上标有1至8的某一数字。棋盘中留有一个空格，空格用0来表示。空格周围的棋子可以移到空格中。要求解的问题是：给出一种初始布局（初始状态）和目标布局（为了使题目简单,设目标状态为123804765），找到一种最少步骤的移动方法，实现从初始布局到目标布局的转变。

输入描述 

Input Description

输入初试状态，一行九个数字，空格用0表示

输出描述 

Output Description

只有一行，该行只有一个数字，表示从初始状态到目标状态需要的最少移动次数(测试数据中无特殊无法到达目标状态数据)

样例输入 

Sample Input

283104765

样例输出 

Sample Output

4

数据范围及提示 

Data Size & Hint

详见试题

分类标签 Tags 

代码有点乱

思路还算清晰

bfs+hash判重

1 #include
      
         2 #include
       
          3 #include
        
           4 using namespace std;  5 const int MAXN=5;  6 int xx[5]={-1,+1,0,0};  7 int yy[5]={
    0,0,-1,+1};  8 struct node  9 { 10     int mp[MAXN][MAXN]; 11 }a[100001]; 12 int hashfind[3733801]; 13 int step[200]; 14 int h=0,t=1; 15 int bc[MAXN][MAXN]={
    {
    0,0,0,0},{
    0,1,2,3},{
    0,8,0,4},{
    0,7,6,5}}; 16 int hash() 17 { 18     int s=0; 19     int k=1; 20     for(int i=1;i<=3;i++) 21     { 22         for(int j=1;j<=3;j++) 23         { 24             s=s+a[t].mp[i][j]*k; 25             k=k*7; 26         } 27     } 28     s=s%3733801; 29     if(hashfind[s]==0) 30     { 31         hashfind[s]=1; 32         return 1; 33     } 34     else 35     { 36         return 0; 37     } 38 } 39 int check() 40 { 41     for(int i=1;i<=3;i++) 42     { 43         for(int j=1;j<=3;j++) 44         { 45             if(a[t].mp[i][j]!=bc[i][j]) 46             return 0; 47         } 48     } 49     return 1; 50 } 51 void move(int x,int y) 52 { 53      54     for(int i=0;i<4;i++) 55     { 56         int wx=x+xx[i]; 57         int wy=y+yy[i]; 58         if(wx>=1&&wx<=3&&wy>=1&&wy<=3) 59         { 60             for(int j=1;j<=3;j++) 61             { 62                 for(int k=1;k<=3;k++) 63                     { 64                         a[t].mp[j][k]=a[h].mp[j][k]; 65                     } 66             } 67             swap(a[t].mp[wx][wy],a[t].mp[x][y]); 68             step[t]=step[h]+1; 69             if(check()==1) 70             { 71                 printf("%d",step[t]); 72                 exit(0);// end 73             } 74             if(hash()==1) 75             t++; 76         } 77     } 78 } 79 void bfs() 80 { 81     while(h