#include <iostream> #include <queue> #include <string.h> #define MAX 10010 #define ex(a) ((a+10)%10) #define pos(a,b,c,d) (a*1000+b*100+c*10+d) using namespace std; int dp[MAX],vis[MAX],a[5]; int dfs[20][4]={{1,0,0,0},{0,1,0,0},{0,0,1,0},{0,0,0,1},{1,1,0,0},{0,1,1,0},{0,0,1,1},{1,1,1,0},{0,1,1,1},{1,1,1,1},{-1,0,0,0},{0,-1,0,0},{0,0,-1,0},{0,0,0,-1},{-1,-1,0,0},{0,-1,-1,0},{0,0,-1,-1},{-1,-1,-1,0},{0,-1,-1,-1},{-1,-1,-1,-1}}; queue<int> q; int main() { memset(vis,0,sizeof(vis)); memset(dp,0,sizeof(dp)); q.push(0); while(!q.empty()) { int tmp=q.front(); q.pop(); for(int i=0,k=tmp;i<4;k/=10)a[i++]=k%10; for(int i=0;i<20;i++) { int p=pos(ex(a[3]+dfs[i][3]),ex(a[2]+dfs[i][2]),ex(a[1]+dfs[i][1]),ex(a[0]+dfs[i][0])); if(p==0)continue; if(dp[p]==0||dp[p]>(dp[tmp]+1)) { dp[p]=(dp[tmp]+1); if(!vis[p]) { vis[p]=1; q.push(p); } } } vis[tmp]=0; } int T; scanf("%d",&T); while(T--) { int num[5],tmp; for(int i=0;i<4;scanf("%d",&num[i++])); for(int i=0;i<4;i++) { scanf("%d",&tmp); num[i]=ex(tmp-num[i]); } printf("%d\n",dp[pos(num[0],num[1],num[2],num[3])]); } return 0; } |
Double click to view unformatted code.