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

点击打开链接uva 652

点击打开链接hdu 1043

点击打开链接zoj 1217

                                                             八数码解法2

解题整体思路 ：    预处理+哈希判重+打表+输出路径

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

                            现在我么考虑如果是单纯的BFS+哈希，如果是多组数据是不是会超时，那么我们是不是想到由于目标状态是一定的，那么对于目标状态而言能够到达的状态是一定的是不会变得，那么这个时候我么就可以预先处理，就是先把那些目标状态能够到达的状态找出，顺便标上目标状态到该状态的路径并且标记该状态哈希值的vis数组为1，那么最后我们就可以做到不用每一次都去搜索，只要把读入的状态的哈希值找出来判断vis数组是否被标记即可，如果有输出路径，我么的路径保存在一个Path[]数组里。 其它详见代码

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

                      2 康托展开的代码

                         int Cantor(int s[] ， int n){
                              int i , j , temp , num;
                              num = 0;
                              for(i = 0 ; i < n ; i++){
                                   temp = 0;
                                   for(j = i+1 ; j < n ; j++){
                                         if(s[j] < s[i]) temp++;//这里是s[j] < s[i];
                                   }
                                   num += factor[n-1-i]*temp;
                             }
                            return num;
                       }

1  uva

#include <algorithm>
#include <iostream>
#include <cstring>
#include <string>
#include <vector>
#include <cstdio>
#include <stack>
#include <queue>
#include <cmath>
using namespace std;
#define MAXN 400000

struct State{
    int state[9];//状态数组
    int pos;//记录空格位置
    string path;//记录从目标状态到当前状态的路径
};
int dir[4][2] = {{-1,0},{0,1},{1,0},{0,-1}};//方向数组
int factor[9] = {1,1,2,6,24,120,720,5040,40320};//阶乘数组
string Path[MAXN];//存储每一个到达目标状态的路径
int vis[MAXN];//判重
char dirtion[4] = {'d' , 'l' , 'u' , 'r'};//对应方向的字符，注意由于是从目标到初始必须是相反输出才能是正确的方向
queue<State>q;

//哈希函数(利用康托展开)X=a[n]*(n-1)!+a[n-1]*(n-2)!+...+a[i]*(i-1)!+...+a[2]*1!+a[1]*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++;//这里是s[j] < s[i];
        }
        num += factor[8-i]*temp;
    }
    return num;
}

//从目标状态出发预处理
void Bfs(){
    while(!q.empty()) q.pop();
    State goal;//目标状态
    memset(vis , 0 , sizeof(vis));//初始化为每一个状态0
    for(int i = 0 ; i < 8 ; i++)
        goal.state[i] = i + 1;
    goal.state[8] = 9;
    goal.path = "" ; goal.pos = 8;
    q.push(goal) ; vis[0] = 1;//目标状态标记为1
    
    while(!q.empty()){
        State cur = q.front();
        q.pop();
        int x , y , r , c;//表示空格的坐标
        x = cur.pos/3 ; y = cur.pos%3;
        for(int i = 0 ; i < 4 ; i++){//四个方向枚举
            r = x + dir[i][0] ; c = y + dir[i][1];
            if(r < 0 || r >= 3 || c < 0 || c >= 3) continue;
            State tmp = cur;
            tmp.state[tmp.pos] = tmp.state[3*r+c];//之前的空格位置换成新的编号
            tmp.pos = 3*r+c;//空格的新位置
            tmp.state[tmp.pos] = 9;
            int hash = Hash(tmp.state);
            
            if(vis[hash]) continue;
            vis[hash] = 1;//标记为1
            tmp.path += dirtion[i];//路径接着加上此时的dirtion[i]
            Path[hash] = tmp.path;//这个状态的路径保存下来
            q.push(tmp);
        }
    }
}



int main(){
    //freopen("input.txt" , "r" , stdin);
    Bfs();
    State star ;
    char c;
    int t;
    scanf("%d" , &t);
    while(t--){
        for(int i = 0 ; i < 9 ; i++){
            scanf(" %c" , &c);
            if(c == 'x') { star.pos = i ; star.state[i] = 9;}
            else star.state[i] = c-'0';
        }
        getchar();
        int hash = Hash(star.state);
        if(vis[hash]){
            for(int i = Path[hash].size()-1 ; i >= 0 ; i--)
                cout<<Path[hash][i];
            printf("\n");
        }
        if(!vis[hash]) printf("unsolvable\n");
        if(t) printf("\n");
    }
    return 0;
}

2  杭电上面是有恶心数据“1 2 3 4 5 6 7 8 x” 应该是输出 unsolvable  ZOJ上面是没有，但是我在POJ上面一直TLE，这就是我比较郁闷的地方过了三个OJ，偏偏POJ不让过

#include <algorithm>
#include <iostream>
#include <cstring>
#include <string>
#include <vector>
#include <cstdio>
#include <stack>
#include <queue>
#include <cmath>
using namespace std;
#define MAXN 400000

struct State{
    int state[9];//状态数组
    int pos;//记录空格位置
    string path;//记录从目标状态到当前状态的路径
};
int dir[4][2] = {{-1,0},{0,1},{1,0},{0,-1}};//方向数组
int factor[9] = {1,1,2,6,24,120,720,5040,40320};//阶乘数组
string Path[MAXN];//存储每一个到达目标状态的路径
int vis[MAXN];//判重
char dirtion[4] = {'d' , 'l' , 'u' , 'r'};//对应方向的字符
queue<State>q;

//哈希函数(利用康托展开)X=a[n]*(n-1)!+a[n-1]*(n-2)!+...+a[i]*(i-1)!+...+a[2]*1!+a[1]*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++;//这里是s[j] < s[i];
        }
        num += factor[8-i]*temp;
    }
    return num;
}

//从目标状态出发预处理
void Bfs(){
    while(!q.empty()) q.pop();
    State goal;//目标状态
    memset(vis , 0 , sizeof(vis));//初始化为每一个状态0
    for(int i = 0 ; i < 8 ; i++)
        goal.state[i] = i + 1;
    goal.state[8] = 9;
    goal.path = "" ; goal.pos = 8;
    q.push(goal) ; vis[0] = 1;//目标状态标记为1
    
    while(!q.empty()){
        State cur = q.front();
        q.pop();
        int x , y , r , c;//表示空格的坐标
        x = cur.pos/3 ; y = cur.pos%3;
        for(int i = 0 ; i < 4 ; i++){//四个方向枚举
            r = x + dir[i][0] ; c = y + dir[i][1];
            if(r < 0 || r >= 3 || c < 0 || c >= 3) continue;
            State tmp = cur;
            tmp.state[tmp.pos] = tmp.state[3*r+c];//之前的空格位置换成新的编号
            tmp.pos = 3*r+c;//空格的新位置
            tmp.state[tmp.pos] = 9;
            int hash = Hash(tmp.state);
            
            if(vis[hash]) continue;
            vis[hash] = 1;//标记为1
            tmp.path += dirtion[i];//路径接着加上此时的dirtion[i]
            Path[hash] = tmp.path;//这个状态的路径保存下来
            q.push(tmp);
        }
    }
}

int main(){
    //freopen("input.txt" , "r" , stdin);
    Bfs();
    State star ;
    char c;
    while(scanf("%c" , &c) != EOF){
        if(c == 'x'){
            star.pos = 0 ; star.state[0] = 9;
        }
        if(c != 'x') star.state[0] = c-'0';
        for(int i = 1 ; i < 9 ; i++){
            scanf(" %c" , &c);
            if(c == 'x') star.pos = i;
            star.state[i] = c-'0';
        }
        getchar();
        int hash = Hash(star.state);
        if(vis[hash]){
            for(int i = Path[hash].size()-1 ; i >= 0 ; i--)
                cout<<Path[hash][i];
            printf("\n");
        }
        else printf("unsolvable\n");
    }
    return 0;
}