洛谷P1379 八数码难题-白红宇

洛谷P1379 八数码难题

阅读量：6480 次

发布时间：2019-06-23

本文共 2575 字，大约阅读时间需要 8 分钟。

1.先用dfs枚举9!的全排列，存到hash数组里（类似离散化），因为顺序枚举，就不需要排序了

2.朴素bfs，判重就用二分找hash；如果发现当前状态=要求状态，输出步数结束程序

上代码

#include
      
       #include
       
        #include
        
         #include
         
          #include
          
           using namespace std;const long long MAXHASH=362885; long long hash[MAXHASH];bool hashbook[MAXHASH];long long hn=0;bool hinit_book[10];long long end=123804765;void hinit(long long step,long long val){    if(step>8){        hn++;        hash[hn]=val;        return;    }    for(int i=0;i<=8;i++){        if(hinit_book[i]==0){            hinit_book[i]=1;            hinit(step+1,val*10+i);            hinit_book[i]=0;        }    }}bool hashput(long long val){    int l=1,r=hn;    for(;;){        if(l==r){            if(hashbook[l]==0){                hashbook[l]=1;                return 1;            }else{                return 0;            }        }        int mid=(l+r)/2;        if(val>hash[mid]){            l=mid+1;        }else{            r=mid;        }    }}struct uct1{    long long data;    long long pos;    long long step;}que[3000000];long long mywap(long long data,long long pa,long long pb){    long long ans=data;        long long df=data%(long long)pow(10,9-pb+1)-data%(long long)pow(10,9-pb);    ans-=df;    ans+=df/pow(10,9-pb)*pow(10,9-pa);        df=data%(long long)pow(10,9-pa+1)-data%(long long)pow(10,9-pa);    ans-=df;    ans+=df/pow(10,9-pa)*pow(10,9-pb);    return ans;}int head=0,tail=0;int main() {    hinit(0,0);    long long pig;    cin>>pig;        int bap=pig;    if(pig==end){        cout<<0;        return 0;    }    int pigpos;    for(pigpos=9;bap>0;pigpos--){        if(bap%10==0){            break;        }        bap=bap/10;    }    if(bap==0){        pigpos=1;    }    head=0;    tail=0;    que[tail].data=pig;    que[tail].pos=pigpos;    que[tail].step=0;    tail++;    for(;head
           
            =1&&que[head].pos<=3&&flag[3]==0){ tdata=mywap(que[head].data,que[head].pos,que[head].pos+3); tpos=que[head].pos+3; flag[3]++; }else if(que[head].pos>=4&&que[head].pos<=6&&flag[4]<2){ if(flag[4]==0){ tdata=mywap(que[head].data,que[head].pos,que[head].pos+3); tpos=que[head].pos+3; }else{ tdata=mywap(que[head].data,que[head].pos,que[head].pos-3); tpos=que[head].pos-3; } flag[4]++; }else if(que[head].pos>=7&&que[head].pos<=9&&flag[5]==0){ tdata=mywap(que[head].data,que[head].pos,que[head].pos-3); tpos=que[head].pos-3; flag[5]++; }else{ break; } if(tdata==end){ cout<