- /*八个数码可能构成的状态共有9!=362880种情况,可以用宽搜的方法,每种状态用一个九位的int来存储,并确保无重复,需要开bool数组来对各种状态进行标记。于是10^8这样大的数组是空间复杂度难以接受。
- 而如果将八数码的所有状态合看作是一个全排列,每一种状态都是一种排列,就可以用康托展开来压缩所有状态,只需开一个大小为9!=362880的数组来存储是否出现重复情况即可。
- 然后康托展开求阶乘没必要一个一个循环,可以用秦九韶算法
- 4*4!+2*3!+2*2!=113
- (((4*4+2)*3+2)*2+1)*1=113
- Have[ ][ ]存储某种状态是否存在
- Line[ ][ ]存储双向宽搜的状态
- Last[ ][ ]存储上一种状态的编号,用来输出路径
- Len[ ]存储双向宽搜的已有状态数
- Mid[ ]找到的答案
- Now[ ]存储当前搜索到的八数码的状态
- Line[0][ ]和line[1][ ]分别为两条队列
- Line[0][now[0]],Line[1][now[1]]为队列的首元素
- Line[0][len[0]],Line[1][len[1]]为队列尾元素*/
- #include#include using namespace std;#define MAXN 370000 int s[10],
- line[2][MAXN],
- len[2],
- now[2],
- have[2][MAXN],
- mid[2],
- last[2][MAXN],
- NUM;
- int p;
- int turn() {
- int result = 0;
- for (int i = 0; i < 9; i++) {
- result *= 10;
- result += s[i];
- }
- return result;
- }
- int cantor() {
- int a = 0,
- b = 0;
- for (int i = 8; i >= 1; i--) { //从后往前枚举每个数
- int b = s[i];
- for (int j = 8; j > i; j--) { //枚举这个数后面的数
- if (s[j] b;
- }
- a += b;
- a *= i;
- }
- return a;
- }
- void get(int num) {
- for (int i = 8; i >= 0; i--) {
- s[i] = num % 10;
- if (s[i] == 0) p = i;
- num /= 10;
- }
- }
- void go(int c, int w) {
- int temp = 0,
- num = 0;
- temp = s[p];
- s[p] = s[p + c];
- s[p + c] = temp; ++len[w];
- line[w][len[w]] = turn();
- num = cantor();
- if (have[w][num] != 0)--len[w];
- else {
- last[w][len[w]] = now[w];
- if (have[!w][num] != 0) {
- mid[w] = len[w];
- mid[!w] = have[!w][num];
- } else have[w][num] = len[w];
- }
- temp = s[p];
- s[p] = s[p + c];
- s[p + c] = temp;
- }
- void out() {
- NUM++;
- /*int cnt=0;
- for(int i=1;i<=3;i++){
- for(int j=1;j<=3;j++){
- cout<<s[cnt];cnt++;
- }cout<<endl;
- }
- cout<<endl;*/
- }
- void out1(int num) {
- if (num != 1) {
- out1(last[0][num]);
- //cout<<"\n";
- }
- get(line[0][num]);
- out();
- }
- void out2(int num) {
- get(line[1][num]);
- if (num != mid[1]) out();
- if (num != 1) {
- //cout<<"\n";
- out2(last[1][num]);
- }
- }
- int main() {
- char ch[10];
- cin >> ch;
- for (int i = 0; i < 9; i++) s[i] = ch[i] - '0';
- int shu = turn();
- int kang = cantor();
- line[0][1] = shu; //正向bfs的第一个状态是初始状态
- len[0] = 1;
- now[0] = 1;
- have[0][kang] = 1;
- s[0] = 1;
- s[1] = 2;
- s[2] = 3;
- s[3] = 8;
- s[4] = 0;
- s[5] = 4;
- s[6] = 7;
- s[7] = 6;
- s[8] = 5;
- shu = turn();
- kang = cantor();
- line[1][1] = shu; //反向bfs的第一个状态是目标状态
- len[1] = 1;
- now[1] = 1;
- if (have[0][kang] == 0) have[1][kang] = 1;
- else {
- cout << 0 << endl;
- }
- while (mid[0] == 0 && (now[0] <= len[0] || now[1] <= len[1])) { //还没出答案,继续搜
- while (mid[0] == 0 && len[1] >= len[0] && now[0] <= len[0]) { //反向bfs的状态数多于正向bfs,就着手正向bfs
- get(line[0][now[0]]);
- //讨论0的位置
- if (p >= 3 && mid[0] == 0) go( - 3, 0); //在后两行,可以上移
- if (p <= 5 && mid[0] == 0) go(3, 0); //在前两行,可以下移
- if (mid[0] == 0 && p >= 1 && (p - 1) % 3 != 2) go( - 1, 0); //在右两列,可以左移
- if (mid[0] == 0 && p <= 8 && (p + 1) % 3 != 0) go(1, 0); //在左两列,可以右移
- ++now[0];
- }
- while (mid[0] == 0 && len[0] >= len[1] && now[1] <= len[1]) {
- get(line[1][now[1]]);
- if (p >= 3 && mid[1] == 0) go( - 3, 1);
- if (p <= 5 && mid[1] == 0) go(3, 1);
- if (mid[1] == 0 && p >= 1 && (p - 1) % 3 != 2) go( - 1, 1);
- if (mid[1] == 0 && p <= 8 && (p + 1) % 3 != 0) go(1, 1); ++now[1];
- }
- }
- out1(mid[0]);
- out2(mid[1]);
- cout < 1;
- }
来源: http://www.bubuko.com/infodetail-1950614.html