首页 > 代码库 > poj 1077 八数码(BFS+康托展开)
poj 1077 八数码(BFS+康托展开)
1 /* 2 题意:八数码问题,给出3*3的矩阵含1~8以及x,给出一个符合的解使得移动后的矩阵的顺序为1~8,最后为x 3 4 题解:BFS 5 需要用到康托展开来表示状态,不然数组无法完全表示所有状态,这样BFS就无法判断找不到解的情况(status 6 的0ms,0KB究竟是怎么做到的,简直不能想象=。=) 7 */ 8 #include <cstdio> 9 #include <cstring> 10 #include <queue> 11 #include <stack> 12 #include <algorithm> 13 14 using namespace std; 15 16 int fac[] = {1,1,2,6,24,120,720,5040,40320,362880}; //i的阶乘为fac[i] 17 /* 康托展开. 18 {1...n}的全排列由小到大有序,s[]为第几个数 */ 19 int KT(int n, int s[]) 20 { 21 int i, j, t, sum; 22 sum = 0; 23 for (i=0; i<n; i++) 24 { 25 t = 0; 26 for (j=i+1; j<n; j++) 27 if (s[j] < s[i]) 28 t++; 29 sum += t*fac[n-i-1]; 30 } 31 return sum+1; 32 } 33 34 /* 康托展开的逆运算. 35 {1...n}的全排列,中的第k个数为s[] */ 36 void invKT(int n, int k, int s[]) 37 { 38 int i, j, t, vst[10]={0}; 39 k--; 40 for (i=0; i<n; i++) 41 { 42 t = k/fac[n-i-1]; 43 for (j=1; j<=n; j++) 44 if (!vst[j]) 45 { 46 if (t == 0) break; 47 t--; 48 } 49 s[i] = j; 50 vst[j] = 1; 51 k %= fac[n-i-1]; 52 } 53 } 54 55 int dir[4][2]={0,1,0,-1,1,0,-1,0}; 56 57 int vis[370000]; 58 char path[370000]; 59 char ansstr[370000]; 60 61 struct node 62 { 63 int state,pdir; 64 int x,y; 65 }Q[370000]; 66 int front,tail; 67 68 int finish_state; 69 70 int bfs(node start) 71 { 72 memset(vis,-1,sizeof(vis)); 73 vis[start.state] = 100000000; 74 front = tail = 0; 75 Q[tail++] = start; 76 while (front < tail) 77 { 78 node now = Q[front++]; 79 if (now.state == finish_state) 80 return finish_state; 81 for(int i=0; i<4; i++) 82 { 83 node tmp = now; 84 if (tmp.pdir != i) 85 { 86 int s[10]; 87 invKT(9,tmp.state,s); 88 89 int x = now.x, y = now.y; 90 int nx = x+dir[i][0],ny = y+dir[i][1]; 91 if (0<=nx&&nx<=2 && 0<=ny&&ny<=2) 92 { 93 swap(s[x*3+y],s[nx*3+ny]); 94 tmp.pdir = i; 95 tmp.x = nx; 96 tmp.y = ny; 97 tmp.state = KT(9,s); 98 if (vis[tmp.state] != -1) 99 continue; 100 Q[tail++] = tmp; 101 vis[tmp.state] = now.state; 102 char c; 103 switch(i) 104 { 105 case 0:c = ‘r‘; break; 106 case 1:c = ‘l‘; break; 107 case 2:c = ‘d‘; break; 108 case 3:c = ‘u‘; break; 109 } 110 path[tmp.state] = c; 111 } 112 } 113 } 114 } 115 return -1; 116 } 117 118 int main(void) 119 { 120 char str[50],tstr[3]; 121 int tmps[9]={1,2,3,4,5,6,7,8,9}; 122 while (~scanf("%s",tstr)) 123 { 124 str[0] = tstr[0]; 125 for(int i=1; i<9; i++) 126 { 127 scanf("%s",tstr); 128 str[i*2] = tstr[0]; 129 } 130 int s[9]; 131 int x; 132 for(int i=0; i<9; i++) 133 { 134 if (‘1‘<=str[i*2] && str[i*2]<=‘9‘) 135 s[i] = str[i*2]-‘0‘; 136 else 137 { 138 s[i] = 9; 139 x = i; 140 } 141 } 142 // 输入略恶心,最后用s[]记录矩阵 143 node start; 144 start.pdir = -1; 145 start.x = x/3; 146 start.y = x%3; 147 start.state = KT(9,s); 148 149 finish_state = KT(9,tmps); 150 int ans = bfs(start); 151 152 if (ans < 0) 153 { 154 printf("unsolvable\n"); 155 } 156 else 157 { 158 int sum = 0; 159 while (vis[finish_state] != -1) 160 { 161 if (vis[finish_state] == 100000000) 162 break; 163 ansstr[sum++] = path[finish_state]; 164 finish_state = vis[finish_state]; 165 } 166 ansstr[sum] = 0; 167 168 for(int i = sum-1; i>=0; i--) 169 printf("%c",ansstr[i]); 170 printf("\n"); 171 } 172 } 173 return 0; 174 }
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。