?
真是水题，感谢HAOI送的福利样例23333
裸BFS，用string做判重，会八数码就会这题。
注意由于队列中状态数很多，一定要把队列的数组开大点！！！
#include #include #include #include #include #include #include #define MAXN 5 using namespace std; map visit; int tmp[MAXN][MAXN],nowstatus[MAXN][MAXN]; int xx[]={1,-1,0,0},yy[]={0,0,1,-1}; bool inMap(int x,int y) { if(x<1||x>4||y<1||y>4) return false; return true; } string GetPermutationFromArray() { string ans=; for(int i=1;i<=4;i++) for(int j=1;j<=4;j++) ans+=tmp[i][j]+'0'; return ans; } void GetArrayFromPermutaion(string s) { int p=0; for(int i=1;i<=4;i++) for(int j=1;j<=4;j++) tmp[i][j]=s[p++]-'0'; } struct node { string status; int step; }q[100000],first,goal; int h=0,t=0; int BFS() { q[t++]=first; visit[first.status]=true; while(h >s; first.status+=s; } for(int i=1;i<=4;i++) { cin>>s; goal.status+=s; } printf(%d ,BFS()); return 0; }