八位数-白红宇

八位数

阅读量：6222 次

发布时间：2019-06-21

本文共 4758 字，大约阅读时间需要 15 分钟。

我真的服了，这题解法是真的多

八位数问题好像还是挺有名的

题目就是给你一个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
     
      #include
      
       #include
       
        #include
        
         #include
         
          #include
          
           #include
           #include
            
             using namespace std;#define ll long long#define se second#define fi first#define oo 0x3fffffffconst 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
             
               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
     
      #include
      
       #include
       
        #include
        
         #include
         
          #include
          
           #include
           #include
            
             using namespace std;#define ll long long#define se second#define fi first#define oo 0x3fffffffconst 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
             
               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("\n");*/ 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("\n");*/ 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\n");}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); }}

转载于:https://www.cnblogs.com/mltang/p/9742744.html

你可能感兴趣的文章