广搜遍历全部情况

#include<bits/stdc++.h>
using namespace std;
string s,ss;long long sum,q;
void bfs(){
    queue<string >que;
    que.push(s);
    map<string ,int >vis;
    vis[s]=1;
    while(que.size()){
        string h=que.front();
        que.pop();
        if(h==ss){
            cout<<vis[ss]-1<<endl;
            return ;
        }
        for(int i=0;i<3;i++){
            string e=h;
            swap(e[i],e[i+1]);
            if(vis[e]==0){
                vis[e]=vis[h]+1;
                que.push(e);
            }
        }
        for(int i=0;i<4;i++){
            string q=h,w=h;
            if(q[i]=='9')q[i]='1';
            else q[i]++;
            if(w[i]=='1')w[i]='9';
            else w[i]--;
            if(vis[q]==0){
                vis[q]=vis[h]+1;
                que.push(q);
            }
            if(vis[w]==0){
                vis[w]=vis[h]+1;
                que.push(w);
            }
        }
    }
}
int main(){
    cin>>q;
	while(q--){
        cin>>s>>ss;
        bfs();
    }
	return 0;
}