1 条题解

  • 1
    @ 2022-7-21 21:00:23
    #include<queue>
    #include<cstdio>
    #include<cstring>
    using namespace std;
    short vis[1000000][7][2];
    struct node{
        int now;
        int stp,pos;
        //pos: 当前光标位置
        bool flag;
    }S,B,f,tmp;
    queue<node>q;
    const int ws[]={1000000,100000,10000,1000,100,10,1};
    inline int UpOrDown(int num,int pos,int chg){
        int t=num/ws[pos]%10+chg;
        if(t>=0&&t<=9)
            return num/ws[pos-1]*ws[pos-1]+t*ws[pos]+num%ws[pos];
        return num;
    }
    inline int Swap(int num,int pos,int chg){
        int bg=num/ws[pos]%10;
        int ed=num/ws[chg]%10;
        if(bg==ed)return num;
        num=num/ws[pos-1]*ws[pos-1]+ed*ws[pos]+num%ws[pos];
        num=num/ws[chg-1]*ws[chg-1]+bg*ws[chg]+num%ws[chg];
        return num;
    }
    int TWBFS(void){
        //TIANWEN BFS(bushi)
        while(!q.empty()){
            tmp=f=q.front();
            tmp.stp++;
            q.pop();
            if(~vis[f.now][f.pos][!f.flag])
                return f.stp+vis[f.now][f.pos][!f.flag];
            //将光标左移一位
            if(f.pos>1){
                tmp.pos=f.pos-1;
                if(vis[tmp.now][tmp.pos][tmp.flag]==-1){
                    vis[tmp.now][tmp.pos][tmp.flag]=tmp.stp;
                    q.push(tmp);
                }
            }
            //将光标右移一位
            if(f.pos<6){
                tmp.pos=f.pos+1;
                if(vis[tmp.now][tmp.pos][tmp.flag]==-1){
                    vis[tmp.now][tmp.pos][tmp.flag]=tmp.stp;
                    q.push(tmp);
                }
            }
            //记得把光标移回来,不要像本蒟蒻一样傻傻踩坑
            tmp.pos=f.pos;
            //将光标所在位置的数值增加1
        	tmp.now=UpOrDown(f.now,f.pos,1);
            if(vis[tmp.now][tmp.pos][tmp.flag]==-1){
                vis[tmp.now][tmp.pos][tmp.flag]=tmp.stp;
                q.push(tmp);
            }
            //将光标所在位置的数值减少1
        	tmp.now=UpOrDown(f.now,f.pos,-1);
            if(vis[tmp.now][tmp.pos][tmp.flag]==-1){
                vis[tmp.now][tmp.pos][tmp.flag]=tmp.stp;
                q.push(tmp);
            }
            //swap0
            if(f.pos!=1){
                tmp.now=Swap(f.now,f.pos,1);
                if(vis[tmp.now][tmp.pos][tmp.flag]==-1){
                    vis[tmp.now][tmp.pos][tmp.flag]=tmp.stp;
                    q.push(tmp);
                }
            }
            //swap1
        	if(f.now!=6){
                tmp.now=Swap(f.now,f.pos,6);
                if(vis[tmp.now][tmp.pos][tmp.flag]==-1){
                    vis[tmp.now][tmp.pos][tmp.flag]=tmp.stp;
                    q.push(tmp);
                }
            }
        }
        return 114514;
    }
    int main(){
        scanf("%d%d",&S.now,&B.now);
        memset(vis,-1,sizeof(vis));
        S.pos=1;
        q.push(S);
        B.flag=1;
        vis[S.now][1][0]=0;
        //最终密码的光标在每一位都有可能出现
        for(int i=1;i<=6;++i){
            B.pos=i;
            vis[B.now][i][1]=0;
            q.push(B);
        }
        printf("%d\n",TWBFS());
        return 0;
    }
    
    • 1

    信息

    ID
    913
    时间
    1000ms
    内存
    125MiB
    难度
    5
    标签
    递交数
    2
    已通过
    2
    上传者