题目描述
在3×3的棋盘上，摆有八个棋子，每个棋子上标有1至8的某一数字。棋盘中留有一个空格，空格用0来表示。空格周围的棋子可以移到空格中。要求解的问题是：给出一种初始布局（初始状态）和目标布局（为了使题目简单,设目标状态为123804765），找到一种最少步骤的移动方法，实现从初始布局到目标布局的转变。
输入输出格式
输入格式：
输入初试状态，一行九个数字，空格用0表示
输出格式：
只有一行，该行只有一个数字，表示从初始状态到目标状态需要的最少移动次数(测试数据中无特殊无法到达目标状态数据)
输入输出样例
输入样例#1：
283104765
输出样例#1：
4
思路
典型的广搜，不过难点在于判断当前的状态。用了一个九位数来记录状态。
代码
1 #include<cstdio> 2 #include<algorithm> 3 #include<set> 4 using namespace std; 5 const int ans=123804765; 6 const int to[5]={1,0,-1,0,1}; 7 set<int>S; 8 struct state 9 { 10 int x,y,step; 11 int w[3][3]; 12 }cur,nxt; 13 state que[1000010]; 14 int calu(state x) 15 { 16 int res=0; 17 for(int i=0;i<3;i++) 18 for(int j=0;j<3;j++) 19 res=res*10+x.w[i][j]; 20 return res; 21 } 22 void bfs(state now) 23 { 24 int head=0,tail=1; 25 que[head]=now; 26 S.clear(); 27 S.insert(calu(now)); 28 while(head<tail) 29 { 30 cur=que[head++]; 31 int xnow=cur.x; 32 int ynow=cur.y; 33 for(int i=0;i<4;i++) 34 { 35 int xx=xnow+to[i]; 36 int yy=ynow+to[i+1]; 37 if(xx<0||yy<0||xx>=3||yy>=3) continue; 38 now=cur; 39 swap(now.w[xx][yy],now.w[xnow][ynow]); 40 now.x=xx; 41 now.y=yy; 42 ++now.step; 43 int tmp=calu(now); 44 if(tmp==ans) 45 { 46 printf("%d",now.step); 47 return; 48 } 49 if(S.find(tmp)==S.end()) 50 que[tail++]=now,S.insert(tmp); 51 } 52 } 53 } 54 int main() 55 { 56 int start; 57 scanf("%d",&start); 58 if(start==ans) 59 { 60 printf("0"); 61 return 0; 62 } 63 for(int i=2;i>=0;i--) 64 for(int j=2;j>=0;j--) 65 { 66 cur.w[i][j]=start%10; 67 start/=10; 68 if(!cur.w[i][j]) 69 cur.x=i,cur.y=j; 70 } 71 cur.step=0; 72 bfs(cur); 73 return 0; 74 }