HDU 1043 Eight（双向BFS+康托展开）
http://acm.hdu.edu.cn/showproblem.php?pid=1043
题意：给出一个八数码，求出到达指定状态的路径。
思路：路径寻找问题。在这道题里用到的知识点挺多的。第一次用双向BFS来做。
①双向BFS
在单向BFS的基础上，多建一个从终止状态开始搜索的队列，当然这个时候需要两个vis[]辅助数组，分别记录两个队列的访问情况，当两个队列相遇时即可终止循环。
②康托展开
X=a[n]*(n-1)!+a[n-1]*(n-2)!+...+a[i]*(i-1)!+...+a[1]*0! ，其中a[i]为当前未出现的元素中是排在第几个（从0开始）。这就是康托展开。
例：321的康托展开为：2*2！+1*1！+0*0！;
（数字3后比3小的数有2个，数字2后比2小的数有1个...依次类推）
③逆序数判断
每次交换两个数字逆序数的奇偶性不变，这个线代里有说过的，这样就可以根据最后状态的逆序数奇偶性来判断当前所给状态能给转换成功。不然的话好像是会超时的。
1 #include<iostream> 2 #include<string> 3 #include<cstring> 4 #include<queue> 5 #include<algorithm> 6 using namespace std; 7 8 const int maxn = 400000; 9 const char* DIR1 = "udlr"; 10 const char* DIR2 = "durl"; 11 12 int fac[] = { 1, 1, 2, 6, 24, 120, 720, 5040, 40320 }; //阶乘值 13 14 int x; //x的位置 15 16 int dir[] = { -3, 3, -1, 1 }; 17 18 int vis1[maxn]; 19 int vis2[maxn]; 20 21 char ss[] = "123456780"; 22 char str[30]; 23 24 struct Node 25 { 26 int x; 27 char str[30]; 28 }; 29 30 struct Step 31 { 32 int cnt; 33 char dir; 34 }pre[maxn]; //记录路径 35 36 37 int sequence(char a[]) //计算康托展开值 38 { 39 int sum = 0; 40 for (int i = 0; i < 9; i++) 41 { 42 int k = 0; 43 for (int j = i + 1; j < 9; j++) 44 { 45 if (a[j] < a[i]) 46 k++; 47 } 48 sum += fac[9 - 1 - i] * k; 49 } 50 return sum; 51 } 52 53 54 void printfff(int x) //追溯到起点输出路径 55 { 56 if (pre[x].cnt == -1) return; 57 printfff(pre[x].cnt); 58 cout << pre[x].dir; 59 } 60 61 int judge(int x, int i) //判断是否越界 62 { 63 int xx = x / 3; //行 64 int yy = x % 3; //列 65 if (i == 3) 66 { 67 int yyy = yy + 1; 68 if (yyy > 2) return 0; 69 } 70 if (i == 2) 71 { 72 int yyy = yy - 1; 73 if (yyy < 0) return 0; 74 } 75 if (i == 1) 76 { 77 int xxx = xx + 1; 78 if (xxx>2) return 0; 79 } 80 if (i == 0) 81 { 82 int xxx = xx - 1; 83 if (xxx < 0) return 0; 84 } 85 return 1; 86 } 87 88 void bfs() 89 { 90 memset(vis1, 0, sizeof(vis1)); 91 memset(vis2, 0, sizeof(vis2)); 92 93 queue<Node> q1, q2; 94 Node p1, p2; 95 96 int count = 2; 97 strcpy(p1.str, str); //初始 98 p1.x = x; //初始x的位置 99 //cout << p1.str << endl; 100 strcpy(p2.str, ss); //终极 101 p2.x = 8; //终极x的位置 102 //cout << p2.str << endl; 103 q1.push(p1); 104 q2.push(p2); 105 vis1[sequence(str)] = 1; 106 vis2[sequence(ss)] = 2; 107 pre[1].cnt = -1; //起点标记 108 pre[2].cnt = -1; //终点标记 109 while (!q1.empty() && !q2.empty()) 110 { 111 Node u = q1.front(); 112 q1.pop(); 113 int p = sequence(u.str); 114 if (vis2[p]) //找到目标状态 115 { 116 printfff(vis1[p]); 117 int k = vis2[p]; 118 while (pre[k].cnt != -1) 119 { 120 cout << pre[k].dir; 121 k = pre[k].cnt; 122 } 123 cout << endl; 124 return; 125 } 126 else //未找到目标状态 127 { 128 Node u2; 129 for (int i = 0; i < 4; i++) 130 { 131 u2 = u; 132 if (!judge(u.x, i)) continue; 133 int xx = u.x + dir[i]; //x的新地址 134 swap(u2.str[u.x], u2.str[xx]); 135 u2.x = xx; 136 int v = sequence(u2.str); 137 if (vis1[v]) continue; //已访问 138 vis1[v] = ++count; 139 pre[count].dir = DIR1[i]; //记录方向 140 pre[count].cnt = vis1[p]; 141 q1.push(u2); 142 } 143 } 144 145 u = q2.front(); 146 q2.pop(); 147 p = sequence(u.str); 148 if (vis1[p]) 149 { 150 printfff(vis1[p]); 151 int k = vis2[p]; 152 while (pre[k].cnt != -1) 153 { 154 cout << pre[k].dir; 155 k = pre[k].cnt; 156 } 157 cout << endl; 158 return; 159 } 160 else //未找到目标状态 161 { 162 Node u2; 163 for (int i = 0; i < 4; i++) 164 { 165 u2 = u; 166 if (!judge(u.x, i)) continue; 167 int xx = u.x + dir[i]; //x的新地址 168 swap(u2.str[u.x], u2.str[xx]); 169 u2.x = xx; 170 int v = sequence(u2.str); 171 if (vis2[v]) continue; //已访问 172 vis2[v] = ++count; 173 pre[count].dir = DIR2[i]; //记录方向 174 pre[count].cnt = vis2[p]; 175 q2.push(u2); 176 } 177 } 178 } 179 cout << "unsolvable" << endl; 180 } 181 182 183 int main() 184 { 185 //freopen("D:\txt.txt", "r", stdin); 186 char s[30]; 187 while (gets(s)) 188 { 189 int k = 0; 190 int t = 0; 191 for (int i = 0; s[i] != NULL; i++) 192 { 193 if (s[i] == 'x') { str[k] = '0'; x = k; } 194 else if (s[i] >= '1' && s[i] <= '8') str[k] = s[i]; 195 else continue; 196 k++; 197 } 198 str[k] = '