题意：这题应该算是经典的八数码问题的弱化版吧：给你一个4x2的方版，上面有0-7 八个数字，每次只能让编号0的方格跟他的上下左右的方格交换；所以也就是把方格0当做空格看待，每次只有空格周围的方格能够向空格处移动。 然后问从输入的方格样式变换到字典序最小的"01234567" 最少需要多少次.
思路：反向BFS。
AC代码：
#include <iostream> #include <iomanip> #include <cstdio> #include <cstring> #include <cstdlib> #include <queue> #include <cmath> #include <map> #include <algorithm> #include <stack> #include <set> //反向bfs using namespace std; map<string ,int> t; int num; int mv[]={-4,4,1,-1};//上下右左 void bfs(string st) { queue<string> q; t[st]=1; q.push(st); while(!q.empty()) { st=q.front(),q.pop(); int num=st.find('0'); for(int i=0;i<4;++i) { int tn=num+mv[i]; if(tn<0||tn>7||num==3&&mv[i]==1||num==4&&mv[i]==-1) continue; string tp=st; swap(tp[num],tp[num+mv[i]]); if(!t[tp]) { q.push(tp); t[tp]=t[st]+1; } } } } int main() { string st="01234567"; bfs(st);//反向BFS while(scanf("%d",&num)!=EOF) { st[0]=num+'0'; for(int i=1;i<8;i++) { scanf("%d",&num); st[i]=num+'0'; } cout<<t[st]-1<<endl; } }
