链接： [Miku]（https://www.luogu.com.cn/problem/P1379）

这个题来说，关键是怎样转换

void deal(int y,int x,int st){
    int li=x;
    if(y%3){

         li=li-(x/qu[y]%10)*qu[y]+((x/qu[y]%10))*qu[y-1];
         q1.push((que){li,st+1});
         li=x; 
    }
    if(y%3!=1){
        li=li-(x/(qu[y-2])%10)*qu[y-2]+(x/qu[y-2]%10)*qu[y-1];
         q1.push((que){li,st+1});
         li=x; 
    } 
    if(y>=4){
        li=li-(x/qu[y-4]%10)*qu[y-4]+(x/qu[y-4]%10)*qu[y-1];
         q1.push((que){li,st+1});
         li=x; 
    }
    if(y<=6){
        li=li-(x/qu[y+2]%10)*qu[y+2]+(x/qu[y+2]%10)*qu[y-1];
         q1.push((que){li,st+1});
         li=x; 
    }
    return ;
}

然后就是一个普普通通的搜索

单向bfs

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<map>
#include<queue>
using namespace std;
map< int,int> m;
struct que{
    int x;
    int st;
}xx;
queue <que> q;
int x; 
int qu[10000]={1,10,100,1000,10000,100000,1000000,10000000,100000000};
void deal(int y,int x,int st){
    int li=x;
    if(y%3){

         li=li-(x/qu[y]%10)*qu[y]+((x/qu[y]%10))*qu[y-1];
         q.push((que){li,st+1});
         li=x; 
    }
    if(y%3!=1){
        li=li-(x/(qu[y-2])%10)*qu[y-2]+(x/qu[y-2]%10)*qu[y-1];
         q.push((que){li,st+1});
         li=x; 
    } 
    if(y>=4){
        li=li-(x/qu[y-4]%10)*qu[y-4]+(x/qu[y-4]%10)*qu[y-1];
         q.push((que){li,st+1});
         li=x; 
    } 
    if(y<=6){
        li=li-(x/qu[y+2]%10)*qu[y+2]+(x/qu[y+2]%10)*qu[y-1];
         q.push((que){li,st+1});
         li=x; 
    }
    return ;
}
int main(){
    m[123804765]=2;
    scanf("%d",&x);
    q.push((que){x,0});
    while(!q.empty()){
        xx=q.front();
        q.pop();
        if(m[xx.x]==2){
            return 0;
        }
        x=xx.x;
        if(m[xx.x])
        continue;
        m[xx.x]=1;
        for(int i=1;i<=9;++i){
            if(x/(qu[i-1])%10==0){
                deal(i,xx.x,xx.st);
            break;              
            }
        }
    }
    return 0;
}

双向更快

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<map>
#include<queue>
using namespace std;
map< int,int> m,stt;
struct que{
    int x;
    int st;
}xx;
queue <que> q1,q2;
int x; 
int qu[10000]={1,10,100,1000,10000,100000,1000000,10000000,100000000};
void deal(int y,int x,int st){
    int li=x;
    if(y%3){

         li=li-(x/qu[y]%10)*qu[y]+((x/qu[y]%10))*qu[y-1];
         q1.push((que){li,st+1});
         li=x; 
    }
    if(y%3!=1){
        li=li-(x/(qu[y-2])%10)*qu[y-2]+(x/qu[y-2]%10)*qu[y-1];
         q1.push((que){li,st+1});
         li=x; 
    } 
    if(y>=4){
        li=li-(x/qu[y-4]%10)*qu[y-4]+(x/qu[y-4]%10)*qu[y-1];
         q1.push((que){li,st+1});
         li=x; 
    }
    if(y<=6){
        li=li-(x/qu[y+2]%10)*qu[y+2]+(x/qu[y+2]%10)*qu[y-1];
         q1.push((que){li,st+1});
         li=x; 
    }
    return ;
}
void deal2(int y,int x,int st){
    int li=x;
    if(y%3){

         li=li-(x/qu[y]%10)*qu[y]+((x/qu[y]%10))*qu[y-1];
         q2.push((que){li,st+1});
         li=x; 
    }
    if(y%3!=1){
        li=li-(x/(qu[y-2])%10)*qu[y-2]+(x/qu[y-2]%10)*qu[y-1];
         q2.push((que){li,st+1});
         li=x; 
    } 
    if(y>=4){
        li=li-(x/qu[y-4]%10)*qu[y-4]+(x/qu[y-4]%10)*qu[y-1];
         q2.push((que){li,st+1});
         li=x; 
    }
    if(y<=6){
        li=li-(x/qu[y+2]%10)*qu[y+2]+(x/qu[y+2]%10)*qu[y-1];
         q2.push((que){li,st+1});
         li=x; 
    }
    return ;
}
int xxx;
int main(){
    scanf("%d",&x);
    q1.push((que){x,0});
    q2.push((que){123804765,0});
    while(1){
        xxx^=1;
    if(xxx){
        xx=q1.front();
        q1.pop();
        if(m[xx.x]==2){
            cout<<stt[xx.x]+xx.st<<endl;
            return 0;
        }
        x=xx.x;
        if(m[xx.x])
        continue;
        m[xx.x]=1;
        stt[xx.x]=xx.st;
        for(int i=1;i<=9;++i){
            if(x/(qu[i-1])%10==0){
                deal(i,xx.x,xx.st);
            break;              
            }
    }
    }else{
        xx=q2.front();
        q2.pop();
        if(m[xx.x]==1){
            cout<<stt[xx.x]+xx.st<<endl;
            return 0;
        }
        x=xx.x;
        if(m[xx.x])
        continue;
        m[xx.x]=2;
        stt[xx.x]=xx.st;
        for(int i=1;i<=9;++i){
            if(x/(qu[i-1])%10==0){
                deal2(i,xx.x,xx.st);
            break;              
            }
        }
    }
    }   
    return 0;
}