题解

#include<bits/stdc++.h>
using namespace std;
int t,n,m,b[4];
struct node{
	int num,step;  
};
void bfs(){
	int vis[10000]={0};
	queue<node> q;
	q.push({n,0});
	vis[n]=1;
	while(!q.empty()){
		node n1=q.front();
		q.pop();
		if(n1.num==m){
			cout<<n1.step<<endl;
			return;
		}
		for(int i=0;i<4;i++){
			b[0]=n1.num/1000,b[1]=n1.num%1000/100,b[2]=n1.num%100/10,b[3]=n1.num%10;
			b[i]++;
			if(b[i]==10) b[i]=1;
			int sum=b[0]*1000+b[1]*100+b[2]*10+b[3]; 
			if(vis[sum]==0){
				vis[sum]=1;
				q.push({sum,n1.step+1});
			} 
		}
		for(int i=0;i<4;i++){
			b[0]=n1.num/1000,b[1]=n1.num%1000/100,b[2]=n1.num%100/10,b[3]=n1.num%10;
			b[i]--;
			if(b[i]==0) b[i]=9;
			int sum=b[0]*1000+b[1]*100+b[2]*10+b[3];
			if(vis[sum]==0){
				vis[sum]=1;
				q.push({sum,n1.step+1});
			} 
		}
		for(int i=0;i<3;i++){
			b[0]=n1.num/1000,b[1]=n1.num%1000/100,b[2]=n1.num%100/10,b[3]=n1.num%10;
			swap(b[i],b[i+1]);
			int sum=b[0]*1000+b[1]*100+b[2]*10+b[3]; 
			if(vis[sum]==0){
				vis[sum]=1;
				q.push({sum,n1.step+1});
			} 
		} 
	}
}
int main(){
	cin>>t;
	while(t--){
		cin>>n>>m; 
		bfs();
	}	
	return 0;
}