首页 > 代码库 > Vijos 八数码问题

Vijos 八数码问题

2024-10-17 10:42:02   213人阅读

背景

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

描述

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

格式

输入格式

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

输出格式

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

样例1

样例输入1

283104765
Copy

样例输出1

4



技术分享
  1 /*  2     搜索过程没什么好说的  3     我只想说一下hash  4     这个判重好坑 数据太细了！  5     只好用康拓展开   6 */  7 #include<cstdio>  8 #include<cstring>   9 #include<iostream> 10 #define MAXN 1000010  11  12 using namespace std; 13  14 int map[3][3],x,y,head,tail; 15  16 int _x[4]={0,1,0,-1}; 17 int _y[4]={1,0,-1,0}; 18  19 struct node { 20     int m[3][3]; 21 }; 22 node e[MAXN]; 23  24 char s[10]; 25  26 int step[MAXN]; 27  28 bool _hash[67338000],flag; 29  30 inline void _pre() { 31     string ss="123804765"; 32     for(int i=0;i<9;i++) { 33         map[x][y]=ss[i]-48; 34         y++; 35         if(y==3) x++,y=0; 36     } 37     x=0;y=0; 38     return; 39 } 40  41 inline bool __hash() { 42     int _Inr=0,k=1,t=1; 43     for(int i=0;i<3;i++) 44       for(int j=0;j<3;j++) { 45           _Inr+=e[tail].m[i][j]*k; 46           t++,k*=t; 47       } 48     //_Inr%=373897779; 49     if(!_hash[_Inr]) { 50         _hash[_Inr]=true; 51         return true; 52     } 53     return false; 54 } 55  56 inline bool pd(int i,int j) { 57     return i>=0&&j>=0&&i<3&&j<3; 58 } 59  60 inline bool check() { 61     for(int i=0;i<3;i++) 62       for(int j=0;j<3;j++)  63         if(e[tail].m[i][j]!=map[i][j]) return false; 64     return true; 65 } 66  67 inline void move(int p,int q) { 68     int xx,yy;  69     for(int i=0;i<4;i++) { 70         xx=p+_x[i]; 71         yy=q+_y[i]; 72         if(pd(xx,yy)) { 73             for(int a=0;a<3;a++) 74               for(int b=0;b<3;b++) 75                 e[tail].m[a][b]=e[head].m[a][b]; 76             swap(e[tail].m[p][q],e[tail].m[xx][yy]); 77             step[tail]=step[head]+1; 78             if(check()) { 79                 printf("%d\n",step[tail]); 80                 flag=true; 81                 return; 82             } 83             if(__hash()) tail++; 84         } 85     } 86 } 87  88 inline void search() { 89     while(head<tail) { 90         for(int i=0;i<3;i++) 91           for(int j=0;j<3;j++) { 92               if(e[head].m[i][j]==0) move(i,j); 93               if(flag) return; 94           } 95         head++; 96     } 97 } 98  99 int main() {100     _pre();101     scanf("%s",s);102     for(int i=0;i<strlen(s);i++) {103         e[0].m[x][y]=s[i]-48;104         y++;105         if(y==3) y=0,x++;106     }107     tail++;108     search();109     return 0;110 }
代码

 

Vijos 八数码问题


联系
我们