HDU 1043 八数码(A*搜索）

在学习八数码A*搜索问题的时候须要知道下面几个点：

Hash：利用康托展开进行hash

康托展开主要就是依据一个序列求这个序列是第几大的序列。

A*搜索：这里的启示函数就用两点之间的曼哈顿距离进行计算就能够。

减枝：在八数码里。随意交换一个空行和一个位置的数字，这个八数码的逆序数是不变的，这样就能够依据眼下状态推断是否可达终点状态了。

第一次做这个题用的map进行哈希，结果果断超时。之后又写了LRJ书上的hash方法也超时了，最后仅仅能用康托展开了

具体请參考：【八数码的八重境地】 http://www.cnblogs.com/goodness/archive/2010/05/04/1727141.html

/*

    康托展开

    A* 算法

    八数码逆序数性质

*/

#include<cmath>

#include<queue>

#include<cstdio>

#include<cstring>

#include<algorithm>

using namespace std;

const int maxn = 370015;

//322560

struct State{

    int mat[3][3];

    int h,g,cvalue;

    int posx,posy;

    friend bool operator < (State p,State q){

        if(p.h != q.h)

            return p.h > q.h;

        else

            return p.g > q.g;

    }

}start;

int  vis[maxn],fa[maxn],cnt;

//-------------------init----------------------------------

void init(){

    memset(vis,-1,sizeof(vis));

    memset(fa,-1,sizeof(fa));

    cnt = 0;

}

bool isok(State &state){

    int temp[9];

    for(int i = 0,k = 0; i < 3; i ++)

        for(int j = 0; j < 3; j++,k++)

            temp[k] = state.mat[i][j];

    int ret = 0;

    for(int i = 0; i < 9; i++)

        for(int j = 0; j < i; j++){

            if(temp[i] && temp[j] && temp[j] > temp[i])

                ret ++;

        }

    return (ret & 1) ? 0 : 1;

}

//---------------------------------------------------------

const int Hash[] = {1,1,2,6,24,120,720,5040,40320};

int Cantor(State &stemp){

    int temp[9];

    for(int i = 0,k = 0; i < 3; i++)

        for(int j = 0; j < 3; j++, k++)

            temp[k] = stemp.mat[i][j];

    int ret = 0;

    for(int i = 0; i < 9; i++){

        int val = 0;

        for(int j = 0; j < i; j++)

            if(temp[j] > temp[i]) val ++;

        ret += Hash[i] * val;

    }

    return ret;

}

//----------------------------------------------------------

int get_h(State &temp){

    int ret = 0;

    for(int i = 0; i < 3; i++)

        for(int j = 0; j < 3; j++){

            ret +=

            abs(i - (temp.mat[i][j] - 1)/3) + abs(j - (temp.mat[i][j] - 1) % 3);

        }

    return ret;

}

//----------------------------------------------------------

//ulldrdrulldrruldlurrd

const char cdir[] = "dlru";

const int dir[4][2] = {{1,0},{0,-1},{0,1},{-1,0}}; //d l r u

void dfs_print(int u){

    if(vis[u] < 0)

        return;

    dfs_print(fa[u]);

    printf("%c",cdir[vis[u]]);

}

bool bfs(){

    priority_queue<State>q;

    start.cvalue = Cantor(start);

    start.h = get_h(start);

    start.g = 0;

    q.push(start);

    vis[start.cvalue] = - 2;

    State temp;

    while(!q.empty()){

        State now = q.top(); q.pop();

        if(now.cvalue == 322560){

            dfs_print(now.cvalue);

            puts("");

            return true;

        }

        for(int i = 0; i < 4; i++){

            temp = now;

            int x = now.posx + dir[i][0];

            int y = now.posy + dir[i][1];

            temp.posx = x;

            temp.posy = y;

            if(x >= 0 && x < 3 && y >= 0 && y < 3){

                swap(temp.mat[x][y],temp.mat[now.posx][now.posy]);

                int cvalue = Cantor(temp);

                if(vis[cvalue] == -1 && isok(temp)){

                    vis[cvalue] = i;

                    fa[cvalue] = now.cvalue;

                    temp.h = get_h(temp);

                    temp.g = now.g + 1;

                    temp.cvalue = cvalue;

                    q.push(temp);

                    if(temp.cvalue == 322560){

                        dfs_print(cvalue);

                        puts("");

                        return true;

                    }

                    cnt ++;

                }

            }

        }

    }

    return false;

}

int main(){

    char _in[10][2];

    while(scanf("%s",_in[0]) != EOF){

        init();

        for(int i = 1; i < 9; i++)

            scanf("%s",_in[i]);

        for(int k = 0,i = 0; i < 3; i++)

            for(int j = 0; j < 3; j++,k ++){

                if(_in[k][0] == 'x'){

                    _in[k][0] = '0';

                    start.posx = i;

                    start.posy = j;

                }

                start.mat[i][j] = _in[k][0] - '0';

            }

        if(!bfs())

            printf("unsolvable\n");

    }

    return 0;

}

/*

1

2

6

24

120

720

5040

40320

*/