[양 방향 BFS 검색]hdu 35678 II

http://acm.hdu.edu.cn/showproblem.php?pid=3567 제목:8 디지털 문제.시작 상태 와 대상 상 태 를 지정 하고 최소 이동 횟수 와 사전 순서 가 가장 작은 방안 을 구 합 니 다.(r:오른쪽으로,l:왼쪽으로,u:위로,d:아래로)
단 방향 BFS–>무한 TLE 로 양 방향 BFS 와 A∗로 검색 할 수 있 으 나 사전 순서 가 가장 작 아야 하기 때문에 양 방향 BFS 든 A∗검색 이 든 가장 먼저 나타 나 는 사전 순서 가 가장 작 다 는 것 을 보장 할 수 없습니다.어 쩔 수 없 이 최소 이동 횟수 를 모두 검색 해 야 했다.쌍방 향 BFS 는 A∗보다 검색 이 빠 르 고,蒟 蒻 가 쓴 쌍방 향 BFS 라 고 합 니 다.
검색 과정 에서 문자열 로 경 로 를 기록 하면 공간 이 너무 큰 것 이 분명 합 니 다.MLE 의...4 진수 로 경 로 를 저장 합 니 다.정방 향 BFS 는 쉽 습 니 다.역방향 으로 부 으 면 어 떡 합 니까?정방 향:path=oldpath∗4+i(0<=i<=3)역방향:path=(3−i)∗4step+oldpath(0<=i<=3)그 중에서 step 는 현재 이동 횟수 를 나타 낸다.
고전적 인 검색 문제그런데......................................................................................↖(^ω^)↗

#include <iostream>
#include <cstdio>
#include <queue>
#include <cstring>
#define LL long long int
#define MAXN 363880
using namespace std;

int power[15]={1,1,2,6,24,120,720,5040,40320,362880,3628800};
char begi[15] ,en[15] ;
int dir[4]={3,-1,1,-3} ,pos_b ,pos_e ;
char word[5]="dlru" ;
int visit[MAXN+10][2] ;
LL road[MAXN+10][2] ,p2[55] ;

struct node
{
    int step ,k ,pos_0 ;
    LL way ;
    char temp[15];
    node(){}
    node(const char a[],const int b,const LL c,const int d,const int e)
    {
        memset(temp,0,sizeof temp);
        strcpy(temp,a);
        step=b ,way=c ,k=d ,pos_0=e ;
    }
}n ;

int Hash(char a[])
{
    int ans=0 ,tmp ;
    for(int i=0;i<9;i++)
    {
        tmp=0;
        for(int j=i+1;j<9;j++)
            if(a[i]>a[j])
                tmp++;
        ans+=tmp*power[8-i];
    }
    return ans;
}

string get_way(LL a,int b)
{
    int str[100] ,cnt=0 ;
    for(int i=1;i<=b;++i)
    {
        str[++cnt]=a%4;
        a/=4;
    }
    string ans="";
    for(int i=cnt;i>0;--i)
        ans+=word[str[i]];
    return ans;
}

void bfs()
{
    if(strcmp(begi,en)==0)
    {
        printf("0

");
        return;
    }
    memset(visit,-1,sizeof visit);
    memset(road,0,sizeof road);

    queue<node>point;
    point.push(node(begi,0,0,0,pos_b));
    visit[Hash(begi)][0]=0;
    point.push(node(en,0,0,1,pos_e));
    visit[Hash(en)][1]=0;

    char temp[15] ;
    int pos_0 ,lin ,pos ,ans=1<<30;
    LL tmp ;
    string anspath="";
    while(!point.empty())
    {
        n=point.front();
        pos_0=n.pos_0 ;
        strcpy(temp,n.temp);
        point.pop();

        for(int i=0;i<4;++i)
        {
            pos=pos_0+dir[i];
            if(pos>-1&&pos<9&&(pos/3==pos_0/3||pos%3==pos_0%3))
            {
                swap(temp[pos_0],temp[pos]);
                lin=Hash(temp);

                if(visit[lin][n.k]!=-1)
                {
                    if(n.step+1>visit[lin][n.k])
                    {
                        swap(temp[pos_0],temp[pos]);
                        continue;
                    }
                    if(n.k)
                        tmp=(3-i)*p2[n.step]+n.way;
                    else tmp=n.way*4+i;
                    road[lin][n.k]=min(road[lin][n.k],tmp);
                }
                else
                {
                    visit[lin][n.k]=n.step+1;
                    if(n.k)
                        road[lin][1]=(3-i)*p2[n.step]+n.way;
                    else road[lin][0]=n.way*4+i;
                }

                if(visit[lin][!n.k]!=-1)
                {
                    string path=get_way(road[lin][0],visit[lin][0])+get_way(road[lin][1],visit[lin][1]);
                    int len=path.size();
                    if(len>ans)
                    {
                        printf("%d
",ans);
                        cout<<anspath<<endl;
                        return;
                    }
                    else if(ans>len)
                    {
                        ans=len;
                        anspath=path;
                    }
                    else if(anspath>path)
                        anspath=path;
                }
                point.push(node(temp,n.step+1,road[lin][n.k],n.k,pos));
                swap(temp[pos_0],temp[pos]);
            }
        }
    }
}

int main()
{
    p2[0]=1;
    for(int i=1;i<=28;++i)
        p2[i]=p2[i-1]*4;
    int T ;
    scanf("%d",&T);
    for(int cas=1;cas<=T;++cas)
    {
        scanf("%s%s",begi,en);
        for(int i=0;i<9;++i)
        {
            if(begi[i]=='X')
                pos_b=i,begi[i]='0';
            if(en[i]=='X')
                pos_e=i,en[i]='0';
        }
        printf("Case %d: ",cas);
        bfs();
    }
    return 0;
}