HDU 1043(逆向BFS)

72 阅读 0 评论 48 点赞

我是靠谱客的博主任性面包，这篇文章主要介绍HDU 1043(逆向BFS)，现在分享给大家，希望可以做个参考。

problem

 1  2  3  4
 5  6  7  8
 9 10 11 12
13 14 15  x

 1  2  3  4     1  2  3  4     1  2  3  4     1  2  3  4
 5  6  7  8     5  6  7  8     5  6  7  8     5  6  7  8
 9  x 10 12     9 10  x 12     9 10 11 12     9 10 11 12
13 14 11 15    13 14 11 15    13 14  x 15    13 14 15  x
            r->            d->            r->

Input

You will receive, several descriptions of configuration of the 8 puzzle. One description is just a list of the tiles in their initial positions, with the rows listed from top to bottom, and the tiles listed from left to right within a row, where the tiles are represented by numbers 1 to 8, plus ‘x’. For example, this puzzle
1 2 3
x 4 6
7 5 8
is described by this list:
1 2 3 x 4 6 7 5 8

Output

You will print to standard output either the word “unsolvable”, if the puzzle has no solution, or a string consisting entirely of the letters ‘r’, ‘l’, ‘u’ and ‘d’ that describes a series of moves that produce a solution. The string should include no spaces and start at the beginning of the line. Do not print a blank line between cases.

Sample Input

2  3  4  1  5  x  7  6  8

Sample Output

ullddrurdllurdruldr

solution

本题就是https://blog.csdn.net/feynman1999/article/details/80089204该题

区别就是HDU上数据是多组然后给了5000ms

上去直接把poj改下提价 T是必然的毕竟一组都是1s级别的

一开始我想问题在于对于一个排列每次都求了散列值，即 $9!*9^2$

那我先求好，岂不是能将后面每一组降到 $9!$ ?

实现时才发现求哈希特喵的还是前面带9*的智障..

后来经某人指点，逆向

这…很自然

多组嘛

倒着求存一下就行

（中间还经历过双向bfs的过程…现在想想有点假，大概率被卡T）
好吧，之前的双向bfs是我写搓了，双向bfs很快的
对于一个原问题是 $4^{30}$ 的问题，双向之后是 $4^{15}*2$ 的时间
空间复杂度增加一倍

对于八数码问题的进一步优化可以采用A*算法，之后补上

example code

#include<bits/stdc++.h>
using namespace std;
int debug_num=0;
#define debug cout<<"debug "<<++debug_num<<" :"

const int maxn=362880;

int fac[10];

bool vis[maxn];

struct node{
    char mapp[3][3];
    int Hash;
    short x,y;
    string path;
};

short dir[4][2]={{0,-1},{0,1},{1,0},{-1,0}};
char walk[5]="lrdu";

node sta;

//unordered_map<int,string> mp1;
char mp1[maxn][40];

void init()
{
    fac[0]=fac[1]=1;
    for(int i=2;i<=9;++i) fac[i]=fac[i-1]*i;
//    int num=0;
//    string t="123456789";
//    do{
//        int tp=0;
//        for(short i=0;i<t.size();++i){
//            tp*=10;
//            tp+=t[i]-'0';
//        }
//        mp[tp]=num++;
//    }while(next_permutation(t.begin(),t.end()));
}

//inline int array_to_int(const node &s)//散列
//{
//    int t=0;
//    for(short i=0;i<3;++i){
//        for(short j=0;j<3;++j){
//        t*=10;
//        t+=s.mapp[i][j]-'0';
//    }
//    }
//    return mp[t];
//}

inline int array_to_int(const node &s)//散列
{
    int ans=0;
    for(short i=1;i<=9;++i){
        int temp=0;
        for(short j=i+1;j<=9;++j) {
            if(s.mapp[(j-1)/3][(j-1)%3]<s.mapp[(i-1)/3][(i-1)%3]) ++temp;
        }
        ans+=temp*fac[9-i];
    }
    return ans;
}

int aim=0;//目标的散列值
string ans_path;

//bool bfs()
//{
//    memset(vis,false,sizeof(vis));
//    queue<node> q;
//    q.push(sta);
//    node now,next;
//    while(!q.empty())
//    {
//        now=q.front();
//        //if(debug_num<10000) debug<<now.x<<" "<<now.y<<" "<<now.path<<endl;
//        q.pop();
//        if(now.Hash==aim){
//            ans_path=now.path;
//            return true;
//        }
//        if(mp1[now.Hash][0]!=0){
//            //cout<<"***"<<endl;
//            ans_path=now.path+mp1[now.Hash];
//            return true;
//        }
//        for(short i=0;i<4;++i){
//            short tx=now.x+dir[i][0];
//            short ty=now.y+dir[i][1];
//            if(tx<0||tx>2||ty<0||ty>2) continue;
//            next=now;
//            next.x=tx;
//            next.y=ty;
//            swap(next.mapp[tx][ty],next.mapp[now.x][now.y]);
//            next.Hash=array_to_int(next);
//            if(!vis[next.Hash]){
//                vis[next.Hash]=true;
//                next.path=next.path+walk[i];
//                q.push(next);
//                if(next.Hash==aim){
//                    ans_path=next.path;
//                    return true;
//                }
//                if(mp1[now.Hash][0]!=0){
//                    //cout<<"***"<<endl;
//                    ans_path=now.path+mp1[now.Hash];
//                    return true;
//                }
//            }
//        }
//    }
//    return false;
//}

void bfs1()
{
    queue<node> q;
    sta.Hash=0;
    for(short i=0;i<=2;++i)
        for(short j=0;j<=2;++j){
            sta.mapp[i][j]=i*3+j+1+'0';
        }
    sta.path="";
    sta.x=2;
    sta.y=2;
    q.push(sta);
    node now,next;
    int num=0;
    while(!q.empty())
    {
        //if(num>362880) return ;
        now=q.front();
        q.pop();
        for(short i=0;i<4;++i){
            short tx=now.x+dir[i][0];
            short ty=now.y+dir[i][1];
            if(tx<0||tx>2||ty<0||ty>2) continue;
            next=now;
            next.x=tx;
            next.y=ty;
            swap(next.mapp[tx][ty],next.mapp[now.x][now.y]);
            next.Hash=array_to_int(next);
            if(mp1[next.Hash][0]==0){
                next.path=next.path+walk[i];
                string tp=next.path;
                reverse(tp.begin(),tp.end());
                for(short j=0;j<tp.size();++j){
                    if(tp[j]=='l') tp[j]='r';
                    else if(tp[j]=='r') tp[j]='l';
                    else if(tp[j]=='u') tp[j]='d';
                    else if(tp[j]=='d') tp[j]='u';
                }
                strcpy(mp1[array_to_int(next)],tp.c_str());//保留信息
                num++;
                q.push(next);
            }
        }
    }
}

int main()
{
    //freopen("in.txt","r",stdin);
    ios::sync_with_stdio(false);
    init();
    bfs1();//先搞一搞反向信息
//    int maxx=0;
//    for(int i=0;i<maxn;++i){
//        int tp=strlen(mp1[i]);
//        maxx=max(maxx,tp);
//    }
//    cout<<maxx<<endl;
//    cout<<"**********************"<<endl;
//    cout<<clock()<<endl;
    char c;
    while(cin>>c)
    {
        if(c=='x'){
            sta.x=0,sta.y=0;
            sta.mapp[0][0]='9';
        }
        else sta.mapp[0][0]=c;
        for(int i=0;i<=2;++i)
            for(int j=0;j<=2;++j){
                if(i==0&&j==0) continue;
                cin>>c;
                if(c=='x'){
                    sta.x=i,sta.y=j;
                    sta.mapp[i][j]='9';//将x当为9
                }
                else sta.mapp[i][j]=c;
        }
        sta.Hash=array_to_int(sta);
//        if(bfs()){
//            if(ans_path.size()==0) cout<<"lr"<<endl;
//            else cout<<ans_path<<endl;
//        }
//        else cout<<"unsolvable"<<endl;
        if(mp1[sta.Hash][0]){
            cout<<mp1[sta.Hash]<<endl;
        }
        else{
            cout<<"unsolvable"<<endl;
        }
    }
    return 0;
}