1   2 #include <cstdio> 3 #include <iostream> 4 #include <queue> 5 #include <cstring> 6 #include <algorithm> 7 using namespace std; 8 const int MAX = 100 + 5; 9 int vis[MAX][MAX][MAX];//标记每一个水杯的状态是否出现过 10 typedef struct Node{11     int cur[3];//当前水杯的状态，就是每个水杯有多少水 12     int step;//由初始状态到当前状态一共需要多少次 13 }Node;14 Node s, e;//s是初始点，e是目标状态点 15 int v[3];//保存三个水杯的容量 16 17 bool match(Node t)18 {19     //判断是否达到最后的状态 20     return (t.cur[0] == e.cur[0] && t.cur[1] == e.cur[1] && t.cur[2] == e.cur[2]); 21 }22 int bfs()23 {24     s.cur[0] = v[0];25     s.cur[1] = s.cur[2] = s.step = 0;26     queue<Node> q;27     Node p;28     memset(vis, 0, sizeof(vis));29     q.push(s);30     vis[v[1]][0][0] = 1;//标记初始状态已经出现过 31     while (!q.empty())32     {33         p = q.front();34         q.pop();35         if (match(p))//如果找到，直接返回它的step 36             return p.step;37         //遍历六种倒水方式 38         for (int i = 0; i < 3; i++)39         {40             for (int j = 0; j < 3; ++j)41             {42                 if (i != j)//自己不能倒给自己水 43                 {44                     /*从i向j水杯中倒水，倒水的量是j水杯的容量将去当前水杯里的水或者是i水杯中有多少水，取他们的最小值45                     因为从i往j中倒水，首先不能倒溜出来，还有就是最多只能把i中的水倒完，就这两种情况，仔细想一下是求他们的最小值*/ 46                     int minn = min(v[j] - p.cur[j], p.cur[i]);47                     Node v = p;//新状态 48                     v.cur[j] += minn;49                     v.cur[i] -= minn;50                     v.step = p.step + 1;//次数加一 51                     if (vis[v.cur[0]][v.cur[1]][v.cur[2]] == 0)//如果以前没有出现过这种状态，就将它入队 52                     {53                         q.push(v);54                         vis[v.cur[0]][v.cur[1]][v.cur[2]] = 1;55                     }56                 }57             }58         }59     }60     return -1;61 }62 int main()63 {64     int T;65     cin >> T;66     while (T--)67     {68         cin >> v[0] >> v[1] >> v[2];69         cin >> e.cur[0] >> e.cur[1] >> e.cur[2];70         cout << bfs() << endl;71     }72     return 0;73 }74