uva 652---Eight Poj 1077 ---Eight zoj 1217---Eight (八数码解法3)

点击打开链接uva 652

点击打开链接hdu 1043

点击打开链接zoj 1217

                                                             八数码解法3

解题整体思路 ：    双向广搜+哈希判重+输出路径

                     (目前只能AC poj 数据水了不解释，其它的OJ一直TLE，求教）

                              我们知道对于八数码问题而言，每一个状态就是每一个格子的编号（我们把空格看成9），那么最多有9!种，那么现在针对每一种状态都有9个数字，难道我们开一个9维数组，显然这个是非常愚蠢的做法当然计算机也是不允许开这么大的数组，那么这时候我么就不能像之前一样去判断状态重复的情况，那我们应该怎么做呢，这时候我们想到了哈希，什么是哈希大家去了解，我们可以把这些个状态压缩成一个整数，然后利用整数去映射就是说每一个整数代表一个状态，那么我么就可以开一个vis数组，利用下标就可以做到映射的效果。哈希是想到了，但是我们应该选择什么哈希函数呢，看了网上一些神牛利用的是"康托展开",也就是利用全排列都有一个对应的整数，利用哈希函数把状态压缩成整数，这样就可以做到每一个整数都是唯一对应一个状态，那么这个时候就把哈希做完了。

                            现在我么考虑如果是单纯的BFS+哈希，如果是多组数据是不是会超时。双向广搜是指，同时从目标状态和初始状态进行广搜，这中间有个优化就是哪一个队列的长度小那么我么优先扩展哪个队列的节点，当有一个扩展节点已经在另外一个队列里面扩展过了，那么我们就可以知道肯定能够从初始状态到目标状态，这样做空间并没有太大的优化，但是时间上理论上可以减少1/2.  我的程序POJ 上面 16ms 其它Hdu 和 uva  zoj 都是TLE（你说双广都超时这奇不奇葩） ，我已经纠结很久了，真的找不到哪个地方使程序挂了，望大伙路过有空可以看看.直接评论即可，小弟不胜感激

参考资料：  1 康托展开：X=an*(n-1)!+an-1*(n-2)!+...+ai*(i-1)!+...+a2*1!+a1*0! 其中，a为整数，并且0<=ai<i(1<=i<=n)。这就是康托展开

                      2 康托展开的代码

代码：

// 双向广搜 + 哈希 + 路径输出
#include <algorithm>
#include <iostream>
#include <cstring>
#include <string>
#include <vector>
#include <cstdio>
#include <cctype>
#include <stack>
#include <queue>
#include <cmath>
using namespace std;
#define MAXN 400000

struct State {
    int state[9];
    int pos;
    char ch1[15]; //记录原始状态到达当前状态的路径(数组不能开太大不然超内存)
    char ch2[15]; //记录目标状态到当前状态的路径(数组不能开太大不然超内存)
} s[MAXN]; //每一个状态对应一个结构
int factor[9] = {1, 1, 2, 6, 24, 120, 720, 5040, 40320}; //阶乘数组
int dir[4][2] = {{-1, 0},{0, 1},{1, 0},{0, -1}}; //方向数组
char dirtion1[4] = {'u', 'r', 'd', 'l'}; //正向搜索
char dirtion2[4] = {'d', 'l', 'u', 'r'}; //逆向搜索
int vis1[MAXN], vis2[MAXN]; //标记某个状态是否被走过vis1是正向
int start; //保存原始输入状态的哈希值
int x , y , c ,r , flag;
State star, goal; //原始状态和目标状态对应的结构体
queue<int>q1;
queue<int>q2;

//初始化goal

void init() {
    goal.pos = 8;
    for (int i = 0; i < 8; i++) goal.state[i] = i + 1;
    goal.state[8] = 9;
    s[0] = goal;
    vis2[0] = 1;
    q2.push(0);
}

//哈希映射
int Hash(int s[]) {
    int i, j, temp, num;
    num = 0;
    for (i = 0; i < 9; i++) {
        temp = 0;
        for (j = i + 1; j < 9; j++) {
            if (s[j] < s[i]) temp++;
        }
        num += factor[8 - i] * temp;
    }
    return num;
}

//扩展函数1
int expand1() {
    State cur = s[q1.front()];
    q1.pop();
    x = cur.pos / 3 ; y = cur.pos % 3;
    r = x ; c = y;
    for (int i = 0; i < 4; i++) {
        r = x + dir[i][0] ; c = y + dir[i][1];
        if (r >= 0 && c >= 0 && r < 3 && c < 3) {
            State tmp = cur;
            tmp.state[tmp.pos] = tmp.state[r * 3 + c];
            tmp.pos = r * 3 + c;
            tmp.state[tmp.pos] = 9;

            int hash = Hash(tmp.state);

            if (!vis1[hash]) {
                vis1[hash] = 1;
                int len = strlen(tmp.ch1);
                tmp.ch1[len] = dirtion1[i]; //更新路径
                if (vis2[hash]) {//如果当前的这个状态被vis2标记过则要输出退出
                    printf("%s", tmp.ch1);
                    for (int i = strlen(s[hash].ch2) - 1; i >= 0; i--)
                        printf("%c", s[hash].ch2[i]);
                    printf("\n") ; flag = 1 ; return 1;
                }
                s[hash] = tmp; //状态复制
                q1.push(hash);
            }
        }
    }
    return 0;
}

//扩展函数2
int expand2() {
    State cur = s[q2.front()];
    q2.pop();
    x = cur.pos / 3 ; y = cur.pos % 3;
    r = x ; c = y;
    for (int i = 0; i < 4; i++) {
        r = x + dir[i][0] ; c = y + dir[i][1];
        if (r >= 0 && c >= 0 && r < 3 && c < 3) {
            State tmp = cur;
            tmp.state[tmp.pos] = tmp.state[r * 3 + c];
            tmp.pos = r * 3 + c;
            tmp.state[tmp.pos] = 9;

            int hash = Hash(tmp.state);

            if (!vis2[hash]) {
                vis2[hash] = 1;
                int len = strlen(tmp.ch2);
                tmp.ch2[len] = dirtion2[i];

                if (vis1[hash]) {//如果该状态在vis1中被标记
                    printf("%s", s[hash].ch1);
                    for (int i = strlen(tmp.ch2) - 1; i >= 0; i--)
                        printf("%c", tmp.ch2[i]);
                    printf("\n") ; flag = 1 ; return 1;
                }
                s[hash] = tmp;
                q2.push(hash);
            }
        }
    }
    return 0;
}

//双向广搜
void DBFS() {
    while (!q1.empty() && !q2.empty()) {
        if (flag) return;
        if (q1.size() <= q2.size()) expand1();  //如果队列1的元素小于等于队列2则扩展队列1
        else expand2();//如果队列2的元素小于队列2则扩展队列2
    }
}
    
//主函数
int main() {
    //freopen("input.txt" , "r" , stdin);
    char c;
    while (scanf("%c", &c) != EOF) {
        if (c == 'x') {
            star.pos = 0 ; star.state[0] = 9;
        } 
        else star.state[0] = c - '0';
        for (int i = 1; i < 9; i++) {
            scanf(" %c", &c);
            if (c == 'x') {
                star.pos = i ; star.state[i] = 9;
            } 
            else star.state[i] = c - '0';
        }
        getchar();
        while (!q1.empty()) q1.pop();
        while (!q2.empty()) q2.pop();
        memset(vis1, 0, sizeof (vis1));
        memset(vis2, 0, sizeof (vis2));
        memset(s, 0, sizeof (s));
        init();
        int hash = Hash(star.state);
        vis1[hash] = 1;
        s[hash] = star;
        q1.push(hash);
        flag = 0;
        if (hash == 0) printf("\n");
        else {
            DBFS();
            if (!flag) printf("unsolvable\n");
        }
    }
    return 0;
}