uva 652---Eight Poj 1077 ---Eight zoj 1217---Eight (八数码解法1）

点击打开链接uva 652

点击打开链接hdu 1043

点击打开链接zoj 1217

                                                             八数码解法1

解题整体思路 ：    单向广搜+哈希判重+输出路径（这种方法效率不高，目前小弟的程序只能过POJ 其它TLE）

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

注意事项：  1 队列里面不能存放结构体而应该存放整型  2 不要用string 用char，string会发去很多的时间

参考资料：  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;
                       }

//思路： 单向bfs()+哈希判重+路径输出(由于POJ数据只有一组，这个方法可以在POJ上面A，其它oj不能A )
#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 ch[50];//记录原始状态到达当前状态的路径(数组不能开太大不然超内存)
}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 dirtion[4] = {'u' , 'r' , 'd' , 'l'};
int  vis[MAXN];//标记某个状态是否被走过
int  start;//保存原始输入状态的哈希值
State star;//原始状态对应的结构体
queue<int>q;//这里不能直接放结构体，不然肯定超时

//哈希映射
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;   
}

//广搜
bool Bfs(){
    while(!q.empty()) q.pop();
    memset(vis , 0 , sizeof(vis));
    start = Hash(star.state);
    vis[start] = 1;
    s[start] = star;
    q.push(start);
    
    while(!q.empty()){
        State cur = s[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 || c < 0 || r >= 3 || 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;
            int len = strlen(cur.ch);//求出前一个状态的路径长度
            tmp.ch[len] = dirtion[i];//更新路径
            s[hash] = tmp;//赋值
            if(hash == 0){//如果搜索到目标节点直接输出退出
               printf("%s\n" , s[hash].ch) ; return 1;
            }          
            q.push(hash);//入对列
        }
    }
    return 0;
}

int main(){ 
    char c;
    while(scanf("%c" , &c) != EOF){
        if(c == 'x'){ star.state[0] = 9 ; star.pos = 0;}
        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();
        int flag = Bfs();
        if(!flag) printf("unsolvable\n");//无解的情况
    }
    return 0;
}