学步园

#include <iostream>
#include <queue>
#include <cstdio>
#include <cstring>
#include <cstdlib>
using namespace std;

typedef struct{
	int num[4];
	int step;
}Number;

int mark[10][10][10][10];

Number first, last;

void BFS(){
	queue<Number> q;
	first.step = 0;
	q.push( first );
	mark[first.num[3]][first.num[2]][first.num[1]][first.num[0]] = 1;

	while( !q.empty() ){
		Number n = q.front();
		q.pop();

		int flag = 1;
		for( int i = 0; i < 4; i++ ){
			if( n.num[i] != last.num[i] ){
				flag = 0;
				break;
			}
		}
		if( flag ){
			cout << n.step << endl;
			return;
		}

		for( int i = 0; i < 4; i++ ){
			Number nn = n;
			nn.step += 1;
			if( nn.num[i] == 9 ){
				nn.num[i] = 1;
			}else{
				nn.num[i] += 1;
			}
			if( mark[nn.num[3]][nn.num[2]][nn.num[1]][nn.num[0]] == 0 ){
				q.push( nn );
				mark[nn.num[3]][nn.num[2]][nn.num[1]][nn.num[0]] = 1;
			}
		}

		for( int i = 0; i < 4; i++ ){
			Number nn = n;
			nn.step += 1;
			if( nn.num[i] == 1 ){
				nn.num[i] = 9;
			}else{
				nn.num[i] -= 1;
			}
			if( mark[nn.num[3]][nn.num[2]][nn.num[1]][nn.num[0]] == 0 ){
				q.push( nn );
				mark[nn.num[3]][nn.num[2]][nn.num[1]][nn.num[0]] = 1;
			}
		}

		for( int i = 3; i >= 1; i-- ){
			Number nn = n;
			nn.step += 1;
			
			int t = nn.num[i];
			nn.num[i] = nn.num[i-1];
			nn.num[i-1] = t;

			if( mark[nn.num[3]][nn.num[2]][nn.num[1]][nn.num[0]] == 0 ){
				q.push( nn );
				mark[nn.num[3]][nn.num[2]][nn.num[1]][nn.num[0]] = 1;
			}
		}

	}
}

int main(){
	char a[5], b[5];
	int t;
	
	cin >> t;
	while( t-- ){
		scanf( "%s", a );
		scanf( "%s", b );
		for( int i = 0; i < 4; i++ ){
			first.num[i] = a[i] - '0';
		}
		for( int i = 0; i < 4; i++ ){
			last.num[i] = b[i] - '0';
		}
		memset( mark, 0, sizeof( mark ) );
		BFS();
	}
	return 0;
}