我真的服了， 这题解法是真的多
八位数问题好像还是挺有名的
题目就是给你一个3*3的矩阵里面填装这 1-8的数字 空了一个格子，我们的目的就是让这个矩阵排列成
1 2 3
4 5 6
7 8 x x是空出来的
方法1： 无脑 map<string,bool> mp，bfs，dfs，巴拉巴拉乱敲就是了，反正我这题这个方法过不了
方法2：把 x看成9，从1 2 3 4 5 6 7 8 9，搜索所有的状态，记录到达所有状态的路径，输入一个起始状态，直接输出路径，好歹能过
这算是比较笨的办法了，我看到网上有很多A*，双向bfs的，深感自己的弱小
对于这个当前状态的保存，我们用了一个叫做康拓展开的东西，这个东西就很劲，具体的你可以看一下康拓展开的百度百科，讲的是很详细了
相当于是做了一个映射
#include<iostream> #include<queue> #include<cstring> #include<vector> #include<cstdio> #include<cmath> #include<map> #include<string> using namespace std; #define ll long long #define se second #define fi first #define oo 0x3fffffff const int maxn = 400000; bool hashs[maxn]; string path[maxn]; int fac[]={1,1,2,6,24,120,720,5040,40320,362880}; int dx[4] = {1,-1,0,0}; int dy[4] = {0,0,1,-1}; char op[5] = "udlr"; struct node { int s[9]; int pos; int val; string path; }; int tocon(int a[]) { int x = 0; for(int i = 0; i <= 8; ++i) { int k = 0; for(int j = i+1; j <= 8; ++j) if(a[j] > a[i]) k ++; x += k*fac[9-i-1]; } return x; } void bfs() { int num[9]; memset(hashs,0,sizeof(hashs)); node st,ed; for(int i = 0; i < 9; ++i) st.s[i] = i+1; st.val = tocon(st.s); st.path = ""; path[st.val] = ""; hashs[st.val] = true; st.pos = 8; queue<node> q; q.push(st); while(!q.empty()) { st = q.front(); q.pop(); for(int i = 0; i < 4; ++i) { int xx = st.pos/3+dx[i]; int yy = st.pos%3+dy[i]; if(xx >= 0 && xx <= 2 && yy >= 0 && yy <= 2) { ed.pos = xx*3 + yy; for(int i = 0; i < 9; ++i) ed.s[i] = st.s[i]; //for(int i = 0 ; i < 9; ++i) // cout << ed.s[i]; //cout << endl; swap(ed.s[ed.pos],ed.s[st.pos]); ed.val = tocon(ed.s); if(!hashs[ed.val]) { hashs[ed.val] = true; ed.path = op[i] + st.path; path[ed.val] = ed.path; q.push(ed); } } } } } int main() { char str[150]; bfs(); while(gets(str)) { int s[9]; int l = 0; for(int i = 0; i < strlen(str); ++i) { if(str[i] <= '9' && str[i] >= '0') s[l++] = str[i] - '0'; else if(str[i] == 'x') s[l++] = 9; } int k = tocon(s); if(hashs[k]) cout << path[k] << endl; else cout << "unsolvable" << endl; } }
方法3 双向bfs
为什么我的双向bfs会超空间啊！不管怎么讲，这个代码还是能够运行的，思路至少是对的，也算是一个方法
#include<iostream> #include<queue> #include<cstring> #include<vector> #include<cstdio> #include<cmath> #include<map> #include<string> using namespace std; #define ll long long #define se second #define fi first #define oo 0x3fffffff const int maxn = 362885; bool hashs1[maxn]; bool hashs2[maxn]; string path1[maxn]; string path2[maxn]; int fac[]={1,1,2,6,24,120,720,5040,40320,362880}; int dx[4] = {-1,0,0,1}; int dy[4] = {0,1,-1,0}; char op1[5] = "urld"; char op2[5] = "dlru"; struct node { int s[9]; int pos; int val; //string path; }; int tocon(int a[]) { int x = 0; for(int i = 0; i <= 8; ++i) { int k = 0; for(int j = i+1; j <= 8; ++j) if(a[j] > a[i]) k ++; x += k*fac[9-i-1]; } return x; } void bfs(int a[9]) { node tmp,t; int c = 0; queue<node> q1,q2; node sc; for(int i = 0; i < 9; ++i) sc.s[i] = i+1; sc.pos=8; sc.val = tocon(sc.s); //sc.path = ""; path1[sc.val] = ""; q2.push(sc); for(int i = 0; i < 9; ++i) { if(a[i] == 9) c = i; tmp.s[i] = a[i]; } tmp.pos = c; tmp.val = tocon(a); //tmp.path = ""; path2[tmp.val] = ""; q1.push(tmp); while(!q1.empty() || !q2.empty()) { int s = q1.size(); while(s--) { tmp = q1.front(); q1.pop(); int pos = tmp.pos; for(int i = 0; i < 4; ++i) { int xx = pos/3 + dx[i]; int yy = pos%3 + dy[i]; if(xx >= 0 && xx <= 2 && yy >= 0 && yy <= 2) { t = tmp; /*cout << "mark1 :" ; for(int i = 0; i < 9; ++i) printf("%d ",t.s[i]); printf(" ");*/ int newpos = xx*3+yy; swap(t.s[pos],t.s[newpos]); t.pos = newpos; t.val = tocon(t.s); path1[t.val] = path1[tmp.val]+op1[i]; if(!hashs1[t.val]) { if(hashs2[t.val] == true) { //cout << "yes" << endl; cout << path1[t.val] + path2[t.val] << endl; return ; } hashs1[t.val] = true; q1.push(t); } } } } s = q2.size(); while(s--) { tmp = q2.front(); q2.pop(); int pos = tmp.pos; for(int i = 0; i < 4; ++i) { int xx = pos/3 + dx[i]; int yy = pos%3 + dy[i]; if(xx >= 0 && xx <= 2 && yy >= 0 && yy <= 2) { t = tmp; /*cout << "mark2 :" ; for(int i = 0; i < 9; ++i) printf("%d ",t.s[i]); printf(" ");*/ int newpos = xx*3+yy; swap(t.s[pos],t.s[newpos]); t.pos = newpos; t.val = tocon(t.s); path2[t.val] = op2[i]+path2[tmp.val]; //cout << t.path << endl; if(!hashs2[t.val]) { if(hashs1[t.val] == true) { //cout << "no" << endl; cout << path1[t.val] + path2[t.val] << endl; return ; } hashs2[t.val] = true; q2.push(t); } } } } } printf("unsolvable "); } int main() { char str[150]; //bfs(); while(gets(str)) { int s[9]; int l = 0; for(int i = 0; i < strlen(str); ++i) { if(str[i] <= '9' && str[i] >= '0') s[l++] = str[i] - '0'; else if(str[i] == 'x') s[l++] = 9; } memset(hashs1,0,sizeof(hashs1)); memset(hashs2,0,sizeof(hashs2)); bfs(s); } }