#include <iostream>#include <string.h>#include <queue>#include <stdlib.h> using namespace std; struct node{ string a; int step;}; int flag[10000] = {0};node N,P;string c, b;queue<node>Q;string adddigit(string , int );string minusdigit(string , int );string changedigit(string , int );void bfs();int main(){ int num; cin >> num; for (int i = 0; i < num; i++) { cin >> c >> b; for (int i = 1111; i < 10000; i++) flag[i] = 0; bfs(); } return 0;}void bfs(){ N.a = c;N.step = 0; while(!Q.empty()) Q.pop(); Q.push(N); flag[atoi(N.a.c_str())] = 1; while (!Q.empty()) { N = Q.front(); Q.pop(); if (N.a == b) break; for (int j = 0; j < 4; j++) for (int i = 0; i < 3; i++) { switch(i) { case 0: P.a = adddigit(N.a, j); if (!flag[atoi(P.a.c_str())]) { P.step = N.step + 1; Q.push(P); flag[atoi(P.a.c_str())] = 1; if (P.a == b) { cout << P.step << endl;; return; } } break; case 1: P.a = minusdigit(N.a, j); if (!flag[atoi(P.a.c_str())]) { P.step = N.step + 1; Q.push(P); flag[atoi(P.a.c_str())] = 1; if (P.a == b) { cout << P.step << endl;; return; } } break; case 2: if (j != 3) P.a = changedigit(N.a, j); if (!flag[atoi(P.a.c_str())]) { P.step = N.step + 1; Q.push(P); flag[atoi(P.a.c_str())] = 1; if (P.a == b) { cout << P.step << endl; return; } } break; } } } cout << N.step << endl;}string adddigit(string a, int n){ if (a[n] == '9') a[n] = '1'; else a[n]++; return a;}string minusdigit(string a, int n){ if (a[n] == '1') a[n] = '9'; else a[n]--; return a;}string changepredigit(string a, int n){ string::value_type temp; temp = a[n]; a[n] = a[n-1]; a[n-1] = temp; return a;}string changedigit(string a, int n){ string::value_type temp; temp = a[n]; a[n] = a[n+1]; a[n+1] = temp; return a;}
