https://daniu.luogu.org/problem/show?pid=1379
题目描述
在3×3的棋盘上，摆有八个棋子，每个棋子上标有1至8的某一数字。棋盘中留有一个空格，空格用0来表示。空格周围的棋子可以移到空格中。要求解的问题是：给出一种初始布局（初始状态）和目标布局（为了使题目简单,设目标状态为123804765），找到一种最少步骤的移动方法，实现从初始布局到目标布局的转变。
输入输出格式
输入格式：
输入初始状态，一行九个数字，空格用0表示
输出格式：
只有一行，该行只有一个数字，表示从初始状态到目标状态需要的最少移动次数(测试数据中无特殊无法到达目标状态数据)
输入输出样例
输入样例#1：
283104765
输出样例#1：
4
BFS搜索每种移动的状态，hash判重
1 #include <cstring> 2 #include <cstdio> 3 #include <queue> 4 5 #define swap(a,b) {int tmp=a; a=b; b=tmp; } 6 const int op[3][3]={{1,2,3}, 7 {8,0,4}, 8 {7,6,5}}; 9 bool vis[387420490]; 10 struct Checkerboard { 11 int step; 12 int map[3][3]; 13 Checkerboard() { step=0; memset(map,0,sizeof(map)); } 14 } u; 15 std::queue<Checkerboard>que; 16 int fx[4]={0,1,0,-1}; 17 int fy[4]={1,0,-1,0}; 18 char s[9]; 19 20 inline bool print(Checkerboard x) 21 { 22 for(int i=0; i<3; ++i) 23 for(int j=0; j<3; ++j) 24 if(x.map[i][j]!=op[i][j]) return 0; 25 return true; 26 } 27 inline int BFS() 28 { 29 que.push(u); 30 for(Checkerboard v; !que.empty(); ) 31 { 32 v=u=que.front(); que.pop(); 33 int tmp=0,t=1,k=1; 34 for(int i=0; i<3; ++i) 35 for(int j=0; j<3; ++j) 36 tmp+=k*u.map[i][j],t++,k*=t; 37 vis[tmp]=0; 38 if(print(u)) return u.step; 39 40 int x,y; 41 for(int i=0; i<3; ++i) 42 for(int j=0; j<3; ++j) 43 if(u.map[i][j]==0) 44 { 45 for(int k=0; k<4; ++k) 46 { 47 x=fx[k]+i,y=fy[k]+j; 48 if(x>=0&&y>=0&&x<3&&y<3) 49 { 50 v.map[i][j]=v.map[x][y]; 51 v.map[x][y]=0; 52 v.step=u.step+1; 53 int tmp=0,t=1,k=1; 54 for(int i=0; i<3; ++i) 55 for(int j=0; j<3; ++j) 56 tmp+=k*v.map[i][j],t++,k*=t; 57 if(!vis[tmp]) 58 vis[tmp]=1,que.push(v); 59 v=u; 60 } 61 } 62 goto STEP; 63 } 64 STEP:; 65 } 66 return 0; 67 } 68 69 int Presist() 70 { 71 scanf("%s",s); 72 for(int i=0; i<3; ++i) u.map[0][i]=s[i]-'0'; 73 for(int i=3; i<6; ++i) u.map[1][i%3]=s[i]-'0'; 74 for(int i=6; i<9; ++i) u.map[2][i%3]=s[i]-'0'; 75 printf("%d ",BFS()); 76 return 0; 77 } 78 79 int Aptal=Presist(); 80 int main(){;}