1
#include<stdio.h>
2#include<stdlib.h>
3#include<string.h>
4
struct ff
{
5
int a,b,c,d;
6 int step;
7 struct ff *next;
8
};
9char hash[20][20][20][20];
10int dir[8][4]={
11
{1,0,0,0},
12 {-1,0,0,0},
13 {0,1,0,0},
14 {0,-1,0,0},
15 {0,0,1,0},
16 {0,0,-1,0},
17 {0,0,0,1},
18 {0,0,0,-1}
19};
20void main()
21{
22 int a,key,kk[4],i,j,s1,s2,s3,s4,min;
23 struct ff *head,*p,*rear;
24 int n;
25 while(scanf("%d%*c",&n)!=EOF)
26 {
27 for(j=0;j<n;j++)
28 {
29 min=99999;
30 p=(struct ff*)malloc(sizeof(struct ff));
31 memset(hash,0,sizeof(hash));
32 scanf("%d%d",&a,&key);
33 kk[3]=key%10;
34 kk[2]=key/10%10;
35 kk[1]=key/100%10;
36 kk[0]=key/1000%10;
37 p->d=a%10;
38 a/=10;
39 p->c=a%10;
40 a/=10;
41 p->b=a%10;
42 a/=10;
43 p->a=a%10;
44 p->step=0;
45 head=p;
46 rear=p;
47 head->next=rear;
48 rear->next=NULL;
49 hash[p->a][p->b][p->c][p->d]=1;
50 while(head)
51 {
52 if(head->a==kk[0]&&head->b==kk[1]&&head->c==kk[2]&&head->d==kk[3])
53 {
54 if(head->step<min)
55 min=head->step;
56 if(head->step==0)break;
57
}
58 for(i=0;i<8;i++)
59 {
60 s1=(head->a+dir[i][0])%10;
61 s2=(head->b+dir[i][1])%10;
62 s3=(head->c+dir[i][2])%10;
63 s4=(head->d+dir[i][3])%10;
64 if(s1==0&&head->a==1)
65 {
66 s1=9;
67 }
68 if(s2==0&&head->b==1)
69 {
70 s2=9;
71 }
72 if(s3==0&&head->c==1)
73 {
74 s3=9;
75 }
76 if(s4==0&&head->d==1)
77 {
78 s4=9;
79 }
80 if(s1==0&&head->a==9)
81 {
82 s1=1;
83 }
84 if(s2==0&&head->b==9)
85 {
86 s2=1;
87 }
88 if(s3==0&&head->c==9)
89 {
90 s3=1;
91 }
92 if(s4==0&&head->d==9)
93 {
94 s4=1;
95 }
96 if(hash[s1][s2][s3][s4]==0)
97 {
98
99 hash[s1][s2][s3][s4]=1;
100 p=(struct ff*)malloc(sizeof(struct ff));
101 p->a=s1;
102 p->b=s2;
103 p->c=s3;
104 p->d=s4;
105 p->step=head->step+1;
106 p->next=NULL;
107 rear->next=p;
108 rear=p;
109 }
110 }
111 s1=(head->b);
112 s2=(head->a);
113 s3=(head->c);
114 s4=(head->d);
115 if(hash[s1][s2][s3][s4]==0)
116 {
117 hash[s1][s2][s3][s4]=1;
118 p=(struct ff*)malloc(sizeof(struct ff));
119 p->a=s1;
120 p->b=s2;
121 p->c=s3;
122 p->d=s4;
123 p->step=head->step+1;
124 p->next=NULL;
125 rear->next=p;
126 rear=p;
127 }
128 s1=(head->a);
129 s2=(head->c);
130 s3=(head->b);
131 s4=(head->d);
132 if(hash[s1][s2][s3][s4]==0)
133 {
134 hash[s1][s2][s3][s4]=1;
135 p=(struct ff*)malloc(sizeof(struct ff));
136 p->a=s1;
137 p->b=s2;
138 p->c=s3;
139 p->d=s4;
140 p->step=head->step+1;
141 p->next=NULL;
142 rear->next=p;
143 rear=p;
144 }
145 s1=(head->a);
146 s2=(head->b);
147 s3=(head->d);
148 s4=(head->c);
149 if(hash[s1][s2][s3][s4]==0)
150 {
151 hash[s1][s2][s3][s4]=1;
152 p=(struct ff*)malloc(sizeof(struct ff));
153 p->a=s1;
154 p->b=s2;
155 p->c=s3;
156 p->d=s4;
157 p->step=head->step+1;
158 p->next=NULL;
159 rear->next=p;
160 rear=p;
161 }
162 if(head->next)
163 head=head->next;
164 else
165 break;
166 }
167 printf("%d\n",min);
168 }
169 }
170}
posted on 2009-01-18 22:22
混沌的云 閱讀(269)
評論(2) 編輯 收藏 引用