hdu 1043 Eight（双向bfs）

题意：经典八数码问题

思路：双向bfs

ps：还有a*算法（还不会）等解法。

代码：

#include<iostream>

#include<stdio.h>

#include<string.h>

#include<queue>

using namespace std;

#define MAXN 362885//最多组合个数：9!=362880

int dir[]={-,,-,};//4个方向移动：u,d,l,r

char opF[]={'u','d','l','r'};//正向bfs操作

char opR[]={'d','u','r','l'};//反向bfs操作

int fac[]={,,,,,,,,};//阶乘

bool visF[MAXN];//正向访问标志

bool visR[MAXN];//

string sTarg="";//目标棋盘

struct node{//存储棋盘信息

    string s;//当前棋盘

    int xLoca;//x位置

}t;

struct node2{//存储操作

    int idF,idR;//正向前驱、反向前驱

    char cF,cR;//操作

}op[MAXN];

int cantor_hash(string s){//康托展开，一共n位

    int n=;//共9位

    int i,j,temp,num;

    num=;

    for(i=;i<n-;i++){//n为位数

        temp=;

        for(j=i+;j<n;j++){

            if(s[j]<s[i])temp++;

        }

        num+=fac[n-(i+)]*temp;

    }

    return num;//从0开始

}

void display(int i){//输出正向操作

    if(op[i].idF==-)return;

    display(op[i].idF);

    printf("%c",op[i].cF);

}

void dBfs(){

    queue<node>qF,qR;//正向队列，反向队列

    node tmp1,tmp2;//棋盘状态临时变量

    int id_hash,id_hash2,xLoca,i;//id 康托哈希下标值，xLoca 暂存x位置

    tmp1=t;//初始状态

    tmp2.s=sTarg;//目标状态

    tmp2.xLoca=;//目标状态x位置

    id_hash=cantor_hash(tmp1.s);//初始状态

    visF[id_hash]=true;

    op[id_hash].idF=-;

    qF.push(tmp1);

    id_hash=cantor_hash(tmp2.s);//目标状态

    visR[id_hash]=true;

    op[id_hash].idR=-;

    qR.push(tmp2);

    while(!qF.empty()&&!qR.empty()){

        //正向bfs

        tmp1=qF.front();

        qF.pop();

        id_hash=cantor_hash(tmp1.s);

        if(visR[id_hash]){//反向bfs也访问过

            display(id_hash);

            id_hash2=id_hash;

            while(op[id_hash2].idR!=-){

                printf("%c",op[id_hash2].cR);

                id_hash2=op[id_hash2].idR;

            }

            printf("\n");

            return;

        }

        for(i=;i<;++i){

            if(i==&&tmp1.xLoca<)continue;

            if(i==&&tmp1.xLoca>)continue;

            if(i==&&tmp1.xLoca%==)continue;

            if(i==&&tmp1.xLoca%==)continue;

            xLoca=tmp1.xLoca+dir[i];

            tmp2=tmp1;

            swap(tmp2.s[tmp1.xLoca],tmp2.s[xLoca]);

            id_hash2=cantor_hash(tmp2.s);

            if(!visF[id_hash2]){

                visF[id_hash2]=true;

                tmp2.xLoca=xLoca;

                op[id_hash2].idF=id_hash;

                op[id_hash2].cF=opF[i];

                qF.push(tmp2);

            }

        }

        //反向bfs

        tmp1=qR.front();

        qR.pop();

        id_hash=cantor_hash(tmp1.s);

        if(visF[id_hash]){//正向bfs也访问过

            display(id_hash);

            id_hash2=id_hash;

            while(op[id_hash2].idR!=-){

                printf("%c",op[id_hash2].cR);

                id_hash2=op[id_hash2].idR;

            }

            printf("\n");

            return;

        }

        for(i=;i<;++i){

            if(i==&&tmp1.xLoca<)continue;

            if(i==&&tmp1.xLoca>)continue;

            if(i==&&tmp1.xLoca%==)continue;

            if(i==&&tmp1.xLoca%==)continue;

            xLoca=tmp1.xLoca+dir[i];

            tmp2=tmp1;

            swap(tmp2.s[tmp1.xLoca],tmp2.s[xLoca]);

            id_hash2=cantor_hash(tmp2.s);

            if(!visR[id_hash2]){

                visR[id_hash2]=true;

                tmp2.xLoca=xLoca;

                op[id_hash2].idR=id_hash;

                op[id_hash2].cR=opR[i];

                qR.push(tmp2);

            }

        }

    }

}

int main(){

    char str[];//串

    int len;//串长度

    int i,j,k;//k 第几个数码

    int ivsNum;//逆序数

    while(~scanf("%[^\n]",str)){

        getchar();//吸收回车

        memset(visF,false,sizeof(visF));

        memset(visR,false,sizeof(visR));

        len=strlen(str);

        t.s="";

        k=;//第几个数码

        for(i=;i<len;++i){//处理字符串

            if(str[i]!=' '){

                if(str[i]=='x'){

                    t.s=t.s+'';

                    t.xLoca=k;

                }

                else t.s=t.s+str[i];

                ++k;//

            }

        }

        ivsNum=;//逆序数初始为0

        for(i=;i<;++i){

            if(t.s[i]=='')continue;

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

                if(t.s[j]=='')continue;

                if(t.s[j]>t.s[i])++ivsNum;

            }

        }

        if(ivsNum&)printf("unsolvable\n");//逆序数为奇数

        else dBfs();//双向bfs

    }

    return ;

}