三个水杯

 1 #include<stdio.h>
 2 #include<queue>
 3 #include<string.h>
 4 using namespace std;
 5 
 6 int c[2][3];
 7 int v[100][100];
 8 typedef struct 
 9 {
10     int vis[3];
11     int deep;
12 }node;
13 
14 int fun()
15 {
16     int i,j,at;
17     queue <node> q;
18     node n,t;
19     memset(v,0,sizeof(v));
20     n.vis[0]=c[0][0];
21     n.vis[1]=n.vis[2]=0;
22     n.deep=0;
23     q.push(n);
24     while(!q.empty())
25     {
26         t=q.front();
27         if(t.vis[0]==c[1][0]&&t.vis[1]==c[1][1]&&t.vis[2]==c[1][2])
28             return t.deep;
29         for(i=0;i<3;i++)
30         {
31             for(j=0;j<3;j++)
32             {
33                 if(i==j) continue;
34                 at=t.vis[i]<c[0][j]-t.vis[j]?t.vis[i]:c[0][j]-t.vis[j];
35                 n=t;
36                 n.vis[i]-=at;
37                 n.vis[j]+=at;
38                 n.deep++;
39                 if(!v[n.vis[1]][n.vis[2]])
40                 {
41                     v[n.vis[1]][n.vis[2]]=1;
42                     q.push(n);
43                 }
44             }
45         }
46         q.pop();
47     }
48     return -1;
49 }
50 
51 int main()
52 {
53     int i,t;
54     scanf("%d",&t);
55     while(t--)
56     {
57         for(i=0;i<3;i++)
58             scanf("%d",&c[0][i]);
59         for(i=0;i<3;i++)
60             scanf("%d",&c[1][i]);
61         printf("%d\n",fun());
62     
63     }
64     return 0;
65 }