比八数码要水的多，bfs。
但是做的时候我把康托展开记错了，wa了好几次。
附上康托展开博客详解：
1 #include2 #include 3 #include 4 #include 5 #include 6 #include 7 #include 8 #define IO ios::sync_with_stdio(false);cin.tie(0); 9 #define INF 0x3f3f3f3f 10 typedef long long ll; 11 using namespace std; 12 int vis[1000010], b[10]; 13 int dir[4][2] = { 1, 0, -1, 0, 0, 1, 0, -1}; 14 int f[10] = { 1, 1, 2, 6, 24, 120, 720, 5040}; 15 typedef struct{ 16 int a[2][4]; 17 int step; 18 }Node; 19 Node node; 20 int kantor(int a[][4])//求法记错了！！ 21 { 22 int k=0, sum=0, t; 23 for(int i = 0; i < 2; i++){ 24 for(int j = 0;j < 4; j++){ 25 b[k++] = a[i][j]; 26 } 27 } 28 for(int i = 0; i < 8; i++){ 29 t = 0; 30 for(int j = i+1; j < 8; j++){ 31 if(b[i]>b[j]) 32 t++; 33 } 34 sum += t*f[8-i-1]; 35 } 36 return sum; 37 } 38 int panduan(int a[][4]) 39 { 40 int k = 0; 41 for(int i = 0; i < 2; i++){ 42 for(int j = 0; j < 4; j++){ 43 if(a[i][j] != k++){ 44 return 0; 45 } 46 } 47 } 48 return 1; 49 } 50 void bfs() 51 { 52 int x, y; 53 queue q; 54 node.step = 0; 55 q.push(node); 56 int tmp = kantor(node.a); 57 vis[tmp] = 1; 58 while(!q.empty()){ 59 Node t = q.front(), p; 60 if(panduan(t.a)){ 61 cout << t.step << endl; 62 break; 63 } 64 65 for(int i = 0; i < 2; i++){ 66 for(int j = 0; j < 4; j++){ 67 if(t.a[i][j] == 0){ 68 x = i; y = j; //0的位置 69 break; 70 } 71 } 72 } 73 p = t; 74 for(int i = 0; i < 4; i++){ 75 int tx = x+dir[i][0]; 76 int ty = y+dir[i][1]; 77 if(tx>=0&&tx<2&&ty>=0&&ty<4){ 78 swap(p.a[tx][ty], p.a[x][y]); 79 tmp = kantor(p.a); 80 if(!vis[tmp]){ 81 vis[tmp] = 1; 82 p.step++; 83 q.push(p); 84 p.step--; 85 } 86 swap(p.a[tx][ty], p.a[x][y]); 87 } 88 } 89 q.pop(); 90 } 91 } 92 int main() 93 { 94 while(cin >> node.a[0][0]){ 95 memset(vis, 0, sizeof(vis)); 96 for(int i = 1; i < 4; i++){ 97 cin >> node.a[0][i]; 98 } 99 for(int i = 0; i < 4; i++){100 cin >> node.a[1][i];101 }102 bfs();103 }104 return 0;105 }