附上题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=1043
我用了3种方法AC。第一种是双向广搜 + 逆序对奇偶剪枝 + 康拓展开 。 第二种方法是打表法，先用bfs搜素出所有路径，保存。当然还有康拓展开。第二种速度快多了。
第三种方法 A*算法 。关于A*算法大家可以参考大神的博客。
第一种 用时 1880MS 代码如下：
#include <bits/stdc++.h> #define MAX 400000 #define N 9 using namespace std; /* 双向广搜，解决八数码问题。 这题还要 进行奇偶剪枝，只有当初态和终态的逆序对和奇偶性相同才有解。 终态逆序对和为0 是偶数，所以在搜索时，某个状态是奇那么肯定不行。不必保存该状态了 */ int fac[] = {1,1,2,6,24,120,720,5040,40320,362880}; char f[]={'r','l','u','d'};//0,1,2,3 左右上下 int fc[4][2]={{0,1},{0,-1},{-1,0},{1,0}}; struct no { int id; short c; }dis[MAX];//记录路径 struct node { string str; int id; node (const string s1,const int t):str(s1),id(t){}; node(){ } }; queue<node> q1; queue<node> q2; int vis[MAX]; string Sstr = "123456789"; string Tstr = "123456789"; string news = "123456789"; int Tstr_id ,Sstr_id; int found = 0; int ANS_t,ANS_o; int op; //奇偶剪枝 bool pruning(string str) { int sum = 0; for (int i=0;i<N;++i) { if (str[i] == '9')continue; for (int j=i+1;j<N;++j) if (str[j]!='9' && str[j]<str[i]) sum++; } if (sum%2) return false; return true; } int kt(string a) { int ans = 0; for (int i = 0;i<N;++i) { int t =0; for (int j=i+1;j<N;++j) if (a[j] < a[i]) t++; ans+= t*fac[N-i-1]; } return ans; } bool change(string & s,int v,int i) { int x = i/3; int y = i%3; int cx = x+fc[v][0]; int cy = y+fc[v][1]; if (cx >=0 && cx < 3 && cy>=0 && cy < 3) { int j = cx*3 + cy; news = s; char t = news[j]; news[j] = news[i]; news[i] = t; //形成新状态后，检测该状态的奇偶性 if (pruning(news)) return true; else return false; } else return false; } int put (int i) { if (i==0) return 1; if (i==1) return 0; if (i==2) return 3; if (i==3) return 2; } //双向bfs 的扩展 void dbfs_expend(node & s,bool Flag,int g,int i) { if (!change(s.str,i,g)) return; int v = kt(news); if (Flag) //正向 { if (vis[v]!=1) { if (vis[v] == 2)//在队列二中出现过，也就是双在此交汇了 { ANS_t = v; ANS_o = s.id; op = i;//衔接操作 found = 1; return ; } vis[v] = 1; dis[v].c = i;dis[v].id = s.id; q1.push(node(news,v)); } } else //反向 { if (vis[v]!=2) { if (vis[v]==1) //交汇了 { ANS_t = s.id; ANS_o = v; op = put(i); found = 1; return ; } vis[v] = 2; dis[v].c = put(i);dis[v].id = s.id; q2.push(node(news,v)); } } } void dbfs() { while(!q1.empty()) q1.pop(); while(!q2.empty()) q2.pop(); node s1(Sstr,Sstr_id); node s2(Tstr,Tstr_id); q1.push(s1); //正向搜索队列 q2.push(s2); //反向搜索队列 vis[Sstr_id] = 1; vis[Tstr_id] = 2; node temp; while(!q1.empty() || !q2.empty()) { if (!q1.empty()) { temp = q1.front();q1.pop(); int g = 0; while(temp.str[g]!='9') ++g; for (int i=0;i<4;++i) { dbfs_expend(temp,true,g,i); if (found) return;//找到了 } } if (!q2.empty()) { temp = q2.front();q2.pop(); int g = 0; while(temp.str[g]!='9') ++g; for (int i=0;i<4;++i) { dbfs_expend(temp,false,g,i); if (found) return ;//找到了 } } } } void init() { memset(vis,0,sizeof(vis)); found = 0; } void putans() { if (!found) printf ("unsolvable "); else { char ans[MAX]; int i = 0; int j = ANS_o; while(j != Sstr_id) { ans[i++] = f[dis[j].c]; j = dis[j].id; } for (int j=i-1;j >= 0; --j) //这里注意，ans数组的存储顺序，很明显，要倒着输出 { printf ("%c",ans[j]); } //中间有个衔接步骤，别忘了输出 printf ("%c",f[op]) ; //接着从 ANS_t 到回去，把从终点出发扩散的道路输出 j = ANS_t; while(j != Tstr_id) { printf ("%c",f[dis[j].c]) ; j = dis[j].id; } printf (" "); } } int main () { char ch; Tstr_id = kt(Tstr); while(cin >> ch) { if (ch == 'x') { Sstr[0]='9'; } else Sstr[0] = ch; for (int i=1;i<=8;++i) { cin >> ch; if (ch == 'x') { Sstr[i] = '9'; } else Sstr[i] = ch; } if(pruning(Sstr)) { Sstr_id = kt(Sstr); init(); dbfs(); putans(); } else printf("unsolvable "); } return 0; } /* ullddrurdllurdruldr ullddrurdllurdruldr */
第二种方法： 最初用的string 来存储状态字符，影响了速度，改为char数组后速度提升了
速度提升不少。可喜可贺啊。
string代码如下
#include <bits/stdc++.h> #define MAX 400000 #define N 9 using namespace std; /* bfs + 打表预处理 + 奇偶剪枝，解决八数码问题。 这题还要 进行奇偶剪枝，只有当初态和终态的逆序对和奇偶性相同才有解。 终态逆序对和为0 是偶数，所以在搜索时，某个状态是奇那么肯定不行。不必保存该状态了 */ int fac[] = {1,1,2,6,24,120,720,5040,40320,362880}; char f[]={'r','l','u','d'};//0,1,2,3 左右上下 int fc[4][2]={{0,1},{0,-1},{-1,0},{1,0}}; struct no { int id; short c; no(){ id = -1;c = -1; } }dis[MAX];//记录路径 struct node { string str; int id; node (const string s1,const int t):str(s1),id(t){}; node(){ } }; queue<node> q1; string Sstr = "123456789"; string Tstr = "123456789"; string news = "123456789"; int Tstr_id ,Sstr_id; int kt(string a) { int ans = 0; for (int i = 0;i<N;++i) { int t =0; for (int j=i+1;j<N;++j) if (a[j] < a[i]) t++; ans+= t*fac[N-i-1]; } return ans; } bool change(string & s,int v,int i) { int x = i/3; int y = i%3; int cx = x+fc[v][0]; int cy = y+fc[v][1]; if (cx >=0 && cx < 3 && cy>=0 && cy < 3) { int j = cx*3 + cy; //计算出移动到的位置的下标 news = s; char t = news[j]; news[j] = news[i]; news[i] = t; return true; } return false; } int put(int i) { if (i==0) return 1; if (i==1) return 0; if (i==2) return 3; if (i==3) return 2; } void bfs() { node s1(Tstr,Tstr_id); q1.push(s1); // dis[Tstr_id].id = Tstr_id; node temp; while(!q1.empty()) { temp = q1.front();q1.pop(); int g = 0; while(temp.str[g]!='9') ++g; for (int i=0;i<4;++i) { if (!change(temp.str,i,g)) continue; int v = kt(news); if (dis[v].id == -1) { dis[v].c = put(i); dis[v].id = temp.id; q1.push(node(news,v)); } } } } void putans() { int j = Sstr_id; while(j != Tstr_id) { printf ("%c",f[dis[j].c]); j = dis[j].id; } printf (" "); } int main () { char ch; Tstr_id = kt(Tstr); bfs(); while(cin >> ch) { if (ch == 'x') { Sstr[0]='9'; } else Sstr[0] = ch; for (int i=1;i<=8;++i) { cin >> ch; if (ch == 'x') { Sstr[i] = '9'; } else Sstr[i] = ch; } Sstr_id = kt(Sstr); if(dis[Sstr_id].id != -1) putans(); else printf("unsolvable "); } return 0; } /* ullddrurdllurdruldr ullddrurdllurdruldr */
char 数组版 最快版本
1 #include <bits/stdc++.h> 2 #define MAX 400000 3 #define N 9 4 using namespace std; 5 /* 6 bfs + 打表预处理 ，解决八数码问题。 7 没有用string 速度快多了 8 */ 9 int fac[] = {1,1,2,6,24,120,720,5040,40320,362880};//康拓展开所需的阶乘 10 int fc[][2]={{1,0},{-1,0},{0,-1},{0,1}}; 11 char f[]="dulr"; 12 13 struct no 14 { 15 int id; //上一个的id 记录下来 16 short c;//操作 17 no() {id = -1;c = -1;} 18 }dis[MAX];//记录路径是结构体 19 20 struct node 21 { 22 char str[10];//状态 23 int id;//状态对应的id 24 node(){} 25 }; 26 27 queue<node> q1; 28 int Tstr_id = 0; 29 int Sstr_id; 30 31 int kt(node a)//康拓展开的计算函数 32 { 33 int ans = 0; 34 for (int i = 0;i<N;++i) 35 { 36 int t =0; 37 for (int j=i+1;j<N;++j) 38 if (a.str[j] < a.str[i]) t++; 39 ans+= t*fac[N-i-1]; 40 } 41 return ans; 42 } 43 44 int put(int i) //因为我们从终态逆着到其他各种能到达的状态，所以，只有倒过来操作， 45 { //在输出答案时就很方便了 46 if (i==0) return 1; 47 if (i==1) return 0; 48 if (i==2) return 3; 49 if (i==3) return 2; 50 } 51 52 void bfs() 53 { 54 node s1; 55 for (int i=0;i<9;++i) s1.str[i] = '0'+i+1;s1.id=0; 56 q1.push(s1); //起点 “123456789” 57 dis[Tstr_id].id = Tstr_id; 58 node temp,v; 59 while(!q1.empty()) 60 { 61 temp = q1.front();q1.pop(); 62 int g = 0; 63 while(temp.str[g]!='9') ++g;//找到'9'的位置 64 for (int i=0;i<4;++i) 65 { 66 v = temp; 67 int cx = g/3+fc[i][0]; 68 int cy = g%3+fc[i][1]; 69 if (cx <0 || cx >= 3 || cy < 0 || cy >= 3) continue; 70 swap(v.str[g],v.str[cx*3 + cy]);//交换，状态变换完成，形成新的状态字符 71 v.id = kt(v); 72 if (dis[v.id].id == -1)//该编号不存在父节点 73 { // 路径的记录 74 dis[v.id].c = put(i); 75 dis[v.id].id = temp.id; 76 q1.push(v); 77 } 78 } 79 } 80 } 81 82 void putans() 83 { 84 int j = Sstr_id; 85 while(j != Tstr_id) 86 { 87 printf ("%c",f[dis[j].c]); 88 j = dis[j].id; 89 } 90 printf (" "); 91 } 92 93 int main () 94 { 95 char ch; 96 bfs(); 97 node s; 98 while(cin >> ch) 99 { 100 if (ch == 'x') 101 s.str[0]='9'; 102 else s.str[0] = ch; 103 for (int i=1;i<=8;++i) 104 { 105 cin >> ch; 106 if (ch == 'x') 107 s.str[i] = '9'; 108 else s.str[i] = ch; 109 } 110 Sstr_id = kt(s); 111 if(dis[Sstr_id].id != -1) 112 putans(); 113 else 114 printf("unsolvable "); 115 } 116 return 0; 117 }
第三种：
A* 算法解决 ，可以参考别人代码，我的乱七八糟的。https://blog.csdn.net/xiaosshhaa/article/details/54315981
大家最好别用string 速度太慢。跑了4400MS，不注意就超时。我改为char [ 10 ] 速度提升很大，1550MS
string 版
1 /* 2 hdu 1043 A* 算法求解 3 f = g + h; 4 */ 5 6 #include <bits/stdc++.h> 7 #define MAX 400000 8 #define N 9 9 using namespace std; 10 11 int fac[] = {1,1,2,6,24,120,720,5040,40320,362880}; 12 char f[]={'d','u','l','r'};//0,1,2,3 左右上下 13 int fc[4][2]={{1,0},{-1,0},{0,-1},{0,1}}; 14 int vis[MAX];//标记该状态是否访问过 15 16 struct no 17 { 18 int fa; 19 short c; 20 no(){ fa = -1;c = -1; 21 } 22 }dis[MAX];//记录路径 23 24 struct node 25 { 26 int g;//已经走的距离 27 int f;//总的值 f = g + h; 28 int h;//预估值 29 int id; 30 string str; 31 node (const string s1,const int t,const int a,const int b,const int c): 32 str(s1),id(t),g(a),h(b),f(c){}; 33 node(){ 34 } 35 bool operator < (const node a1)const //重载比较运算符，优先队列按此排列。 36 { //这里一定要加上const !! 37 if (a1.f != f) return a1.f < f; 38 return a1.g < g; 39 } 40 }; 41 42 priority_queue<node> q1; 43 44 string Sstr = "123456789"; 45 string Tstr = "123456789"; 46 int Tstr_id ,Sstr_id; 47 48 int kt(string a) 49 { 50 int ans = 0; 51 for (int i = 0;i<N;++i) 52 { 53 int t =0; 54 for (int j=i+1;j<N;++j) 55 if (a[j] < a[i]) t++; 56 ans+= t*fac[N-i-1]; 57 } 58 return ans; 59 } 60 61 //返回出A*算法所需的预估值 62 // 我们以1~8数字回到最终位置要移动的次数，就单纯的算出它与最终位置的距离。 63 // 算出的值肯定 比实际操作小，这样保证了答案的正确性。 64 int getH(string str) 65 { 66 int sum = 0; 67 int x,y,cx,cy; 68 for (int i=0;i<N;++i) 69 { 70 x = i/3;y=i%3; 71 cx = (str[i]-'1')/3; 72 cy = (str[i]-'1')%3; 73 sum +=abs(x-cx)+abs(y-cy); 74 } 75 return sum; 76 } 77 //奇偶剪枝 ，判断逆序数的奇偶 78 bool pruning(string str) 79 { 80 int sum = 0; 81 for (int i=0;i<N;++i) 82 { if (str[i] == '9')continue; 83 for (int j=i+1;j<N;++j) 84 if (str[j]!='9' && str[j]<str[i]) 85 sum++; 86 } 87 if (sum%2) return false; 88 return true; 89 } 90 91 bool change(string & s,int v,int i)//引用 92 { 93 int x = i/3; 94 int y = i%3; 95 int cx = x+fc[v][0]; 96 int cy = y+fc[v][1]; 97 if (cx >=0 && cx < 3 && cy>=0 && cy < 3) 98 { 99 int j = cx*3 + cy; //计算出移动到的位置的下标 100 swap(s[i],s[j]);//交换，状态变换完成， 101 return pruning(s); 102 } 103 return false; 104 } 105 106 void Astar() 107 { 108 while(!q1.empty()) q1.pop(); 109 int h = getH(Sstr); 110 node s1(Sstr,Sstr_id,0,h,h); 111 q1.push(s1); 112 // dis[Sstr_id].fa = Sstr_id; 113 vis[Sstr_id] = 1; 114 node u,v; 115 while(!q1.empty()) 116 { 117 u = q1.top();q1.pop(); 118 int g = 0; 119 while(u.str[g]!='9') ++g; 120 for (int i=0;i<4;++i) 121 { 122 v = u;//这样，后面直接v.g++即可 123 if (!change(v.str,i,g)) continue;//该状态无法生成或者逆序对数为奇； 124 v.id = kt(v.str); 125 if (vis[v.id]) continue;//该状态访问过了，排除 126 vis[v.id] = 1; 127 v.h = getH(v.str); 128 v.g++;//在父节点基础上又走了一步 129 v.f = v.h+v.g; 130 dis[v.id].c = i; 131 dis[v.id].fa = u.id; 132 q1.push(v);//入堆 133 if (v.id == Tstr_id) return ;//已经走到了 134 } 135 } 136 } 137 stack<char> sta;//输出答案时辅助 138 void putans() 139 { 140 int j = Tstr_id; 141 while(j != Sstr_id) 142 { 143 sta.push(f[dis[j].c]); 144 j = dis[j].fa; 145 } 146 while(!sta.empty()) 147 {printf ("%c",sta.top());sta.pop();} 148 printf (" "); 149 } 150 151 int main () 152 { 153 char ch; 154 Tstr_id = kt(Tstr); 155 while(cin >> ch) 156 { 157 if (ch == 'x') 158 { 159 Sstr[0]='9'; 160 } 161 else Sstr[0] = ch; 162 for (int i=1;i<=8;++i) 163 { 164 cin >> ch; 165 if (ch == 'x') 166 { 167 Sstr[i] = '9'; 168 } 169 else Sstr[i] = ch; 170 } 171 Sstr_id = kt(Sstr); 172 if(pruning(Sstr)) 173 { 174 memset(vis,0,sizeof(vis)); 175 Astar(); 176 putans(); 177 } 178 else 179 printf("unsolvable "); 180 } 181 return 0; 182 } 183 /* 184 ullddrurdllurdruldr 185 ullddrurdllurdruldr 186 */
数组
/* hdu 1043 A* 算法求解 f = g + h; */ //#include <bits/stdc++.h> #include <stdio.h> #include <string.h> #include <queue> #include <algorithm> #include <iostream> #define MAX 400000 #define N 9 using namespace std; int fac[] = {1,1,2,6,24,120,720,5040,40320,362880}; char f[]={'d','u','l','r'};//0,1,2,3 左右上下 int fc[4][2]={{1,0},{-1,0},{0,-1},{0,1}}; int vis[MAX];//标记该状态是否访问过 struct no { int fa; short c; }dis[MAX];//记录路径 struct node { int g;//已经走的距离 int f;//总的值 f = g + h; int h;//预估值 int id; char str[10]; bool operator < (const node a1)const //重载比较运算符，优先队列按此排列。 { //这里一定要加上const !! if (a1.f != f) return a1.f < f; return a1.g < g; } }; priority_queue<node> q1; int Tstr_id = 0; int Sstr_id; int kt(node s1) { int ans = 0; for (int i = 0;i<N;++i) { int t =0; for (int j=i+1;j<N;++j) if (s1.str[j] < s1.str[i]) t++; ans+= t*fac[N-i-1]; } return ans; } //返回出A*算法所需的预估值 // 我们以1~8数字回到最终位置要移动的次数，就单纯的算出它与最终位置的距离。 // 算出的值肯定 比实际操作小，这样保证了答案的正确性。 int getH(node s1) { int sum = 0; int x,y,cx,cy; for (int i=0;i<N;++i) { x = i/3;y=i%3; cx = (s1.str[i]-'1')/3; cy = (s1.str[i]-'1')%3; sum +=abs(x-cx)+abs(y-cy); } return sum; } //奇偶剪枝 ，判断逆序数的奇偶 bool pruning(node s1) { int sum = 0; for (int i=0;i<N;++i) { if (s1.str[i] == '9')continue; for (int j=i+1;j<N;++j) if (s1.str[j]!='9' && s1.str[j]<s1.str[i]) sum++; } if (sum%2) return false; return true; } void Astar() { node u,v; while(!q1.empty()) { u = q1.top();q1.pop(); int g = 0; while(u.str[g]!='9') ++g; for (int i=0;i<4;++i) { v = u;//这样，后面直接v.g++即可 int cx = g/3+fc[i][0]; int cy = g%3+fc[i][1]; if (cx <0 || cx >= 3 || cy < 0 || cy >= 3) continue; swap(v.str[g],v.str[cx*3 + cy]);//交换，状态变换完成， if ( !pruning(v)) continue;//此状态逆序数为奇数，舍弃 v.id = kt(v); if (vis[v.id]) continue;//该状态访问过了，排除 vis[v.id] = 1; v.h = getH(v); v.g++;//在父节点基础上又走了一步 v.f = v.h+v.g; dis[v.id].c = i; dis[v.id].fa = u.id; q1.push(v);//入堆 if (v.id == Tstr_id) return ;//已经走到了 } } } void putans(int j) { if (j != Sstr_id) putans(dis[j].fa); else return ; printf ("%c",f[dis[j].c]); } int main () { char ch; node s1; while(cin >> ch) { if (ch == 'x') s1.str[0]='9'; else s1.str[0] = ch; for (int i=1;i<=8;++i) { cin >> ch; if (ch == 'x') s1.str[i] = '9'; else s1.str[i] = ch; } Sstr_id = kt(s1); if(pruning(s1)) { memset(vis,0,sizeof(vis)); while(!q1.empty()) q1.pop(); s1.g=0;s1.h= getH(s1);s1.f= s1.g+s1.h;s1.id = Sstr_id; q1.push(s1); vis[Sstr_id] = 1;//标记 Astar(); putans(Tstr_id);printf (" "); } else printf("unsolvable "); } return 0; } /* ullddrurdllurdruldr ullddrurdllurdruldr */
非常经典的题目，建议大家做做，很多种解决方法，有很多优秀博客参考。