三个水杯

 1 #include <cstdio>
 2 #include <cstring>
 3 #include <queue>
 4 
 5 using namespace std;
 6 struct node {
 7     int wat[3]; //记录中间过程状态
 8     int step;//最小倒水次数。
 9 };
10 int cup[3];
11 int res[3];
12 int vis[110][110];//标志状态。
13 void bfs(int sx,int sy,int sz)
14 {
15     memset(vis,0,sizeof(vis));
16     queue<node> dl;
17     node a,b;
18     a.wat[0]=sx;    a.wat[1]=sy;    a.wat[2]=sz;
19     vis[sx][sy]=1;
20     a.step=0;
21     dl.push(a);
22     while(!dl.empty())
23     {
24         a=dl.front();
25         dl.pop();
26         if(a.wat[0]==res[0]&&a.wat[1]==res[1]&&a.wat[2]==res[2])
27         {
28             printf("%d
",a.step);
29             return;
30         }
31         for(int i=0;i<3;i++)
32             for(int j=0;j<3;j++)
33         {
34             b=a;
35             b.step++;
36             if(i!=j)
37             {
38                 if(a.wat[i]+a.wat[j]<=cup[i])
39                 {
40                     b.wat[i]=a.wat[i]+a.wat[j];
41                     b.wat[j]=0;
42                 }
43                 else{
44                         b.wat[i]=cup[i];
45                         b.wat[j]=a.wat[j]-(cup[i]-a.wat[i]);
46                 }
47                 if(b.wat[0]==res[0]&&b.wat[1]==res[1]&&b.wat[2]==res[2])
48                 {
49                     printf("%d
",b.step);
50                     return ;
51                 }
52                 if(!vis[b.wat[0]][b.wat[1]])
53                     dl.push(b);
54                 vis[b.wat[0]][b.wat[1]]=1;
55             }
56         }
57     }
58     printf("-1
");
59 }
60 
61 int main()
62 {
63     int n;
64     scanf("%d",&n);
65     while(n--)
66     {
67         for(int i=0;i<3;i++)
68             scanf("%d",&cup[i]);
69         for(int j=0;j<3;j++)
70             scanf("%d",&res[j]);
71         bfs(cup[0],0,0);
72     }
73     return 0;
74 }
75
View Code