这个题如果裸搜肯定超时了
但是我们可以枚举，用初始串的哪一位数字去填目标串的那一位数字
这样就是暴力6！，复杂度很低，然后需要解决过程中经过的点的问题，
因为是从左向右走，所以记录当前光标，
和当前达到的最右端
所以复杂度是O(T*36*(6!)),2000w的复杂度
#include <cstdio> #include <cstring> #include <algorithm> #include <iostream> #include <cstdlib> #include <vector> #include <cmath> #include <queue> #include <map> #include <string> using namespace std; typedef long long LL; const int N=1e6+5; const int INF=0x3f3f3f3f; int vis[N][7][7]; int f[]= {100000,10000,1000,100,10,1}; int left(int x,int p) { int k1=x/f[p]%10; int k2=x/f[p-1]%10; return x+(k2-k1)*f[p]+(k1-k2)*f[p-1]; } int right(int x,int p) { return left(x,p+1); } int judge(int x,int y,int l,int r) { int ret=0; for(int i=l; i<=r; ++i) ret+=abs((x/f[i]%10)-(y/f[i]%10)); return ret; } struct Node { int x,p,mx,step; Node() {} Node(int a,int b,int c,int d) { x=a; p=b; mx=c; step=d; } }; queue<Node>q; int main() { int T; scanf("%d",&T); while(T--) { int s,t; scanf("%d%d",&s,&t); q.push(Node(s,0,0,0)); vis[s][0][0]=++T; int ans=INF; while(!q.empty()) { Node u=q.front(); q.pop(); if(u.step>=ans)continue; if(u.p>0) { Node v=u;++v.step; --v.p; if(vis[v.x][v.p][v.mx]!=T) { vis[v.x][v.p][v.mx]=T; q.push(v); } } if(u.p<5) { Node v=u; ++v.p;++v.step; v.mx=max(v.mx,v.p); if(vis[v.x][v.p][v.mx]!=T) { vis[v.x][v.p][v.mx]=T; if(judge(v.x,t,v.mx+1,5)==0) ans=min(ans,judge(v.x,t,0,v.mx)+v.step); q.push(v); } } if(u.p>0) { Node v=u;++v.step; v.x=left(v.x,v.p); if(vis[v.x][v.p][v.mx]!=T) { vis[v.x][v.p][v.mx]=T; if(judge(v.x,t,v.mx+1,5)==0) ans=min(ans,judge(v.x,t,0,v.mx)+v.step); q.push(v); } } if(u.p<5) { Node v=u;++v.step; v.x=right(v.x,v.p); v.mx=max(v.mx,v.p+1); if(vis[v.x][v.p][v.mx]!=T) { vis[v.x][v.p][v.mx]=T; if(judge(v.x,t,v.mx+1,5)==0) ans=min(ans,judge(v.x,t,0,v.mx)+v.step); q.push(v); } } } --T; printf("%d ",ans); } return 0; }