hdu 1495 非常可乐(bfs)

参考：https://blog.csdn.net/qq_34374664/article/details/51646060

非常可乐

Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 28191 Accepted Submission(s): 10924

Problem Description

大家一定觉的运动以后喝可乐是一件很惬意的事情，但是seeyou却不这么认为。因为每次当seeyou买了可乐以后，阿牛就要求和seeyou一起分享这一瓶可乐，而且一定要喝的和seeyou一样多。但seeyou的手中只有两个杯子，它们的容量分别是N 毫升和M 毫升可乐的体积为S （S<101）毫升　(正好装满一瓶) ，它们三个之间可以相互倒可乐 (都是没有刻度的，且 S==N+M，101＞S＞0，N＞0，M＞0) 。聪明的ACMER你们说他们能平分吗？如果能请输出倒可乐的最少的次数，如果不能输出"NO"。

Input

三个整数 : S 可乐的体积 , N 和 M是两个杯子的容量，以"0 0 0"结束。

Output

如果能平分的话请输出最少要倒的次数，否则输出"NO"。

Sample Input

7 4 3

4 1 3

0 0 0

Sample Output

  1 #include<iostream>
  2 #include<cstring>
  3 #include<vector>
  4 #include<queue>
  5 #include<stdio.h>　
  6 
  7 using namespace std;
  8 
  9 int bottle[3];             // bottle[0]表示刚开始装可乐的瓶子的体积，即S；[1]和[2]表示其他两个瓶子的体积，即N,M
 10 int vis[101][101][101];     // 标记该种局面是否被访问过
 11 int half;
 12 
 13 struct node
 14 {
 15     int cur[3];        // cur[0]表示当前局面可乐瓶中水的体积，cur[1]和cur[2]表示当前局面其他两个瓶子中水的体积
 16     int step;        // bfs中的层数
 17 }p, t;
 18 
 19 void bfs()
 20 {
 21     p.cur[0] = bottle[0];        // 一开始可乐瓶装满了水
 22     p.cur[1] = p.cur[2] = 0;    // 其他两个瓶子一开始是空的
 23     p.step = 0;
 24 
 25     queue<node> Q;
 26     Q.push(p);        // 初始局面入队
 27     vis[p.cur[0]][p.cur[1]][p.cur[2]] = 1;
 28 
 29     while (!Q.empty())
 30     {
 31         p = Q.front();
 32         Q.pop();
 33 
 34         if ((half == p.cur[0] && half == p.cur[1]) || (half == p.cur[0] && half == p.cur[2]) || (half == p.cur[1] && half == p.cur[2]))
 35         {
 36             cout << p.step << endl;
 37             return;
 38         }
 39 
 40         // 注意这双重循环内的都是p的下一层，都是属于同一层的！
 41         for (int i = 0; i < 3; ++i)
 42         {
 43             if (p.cur[i] > 0)    // 当前瓶子里必须有水
 44             {
 45                 for (int j = 0; j < 3; ++j)
 46                 {
 47                     if (i == j)
 48                         continue;
 49 
 50                     t = p;    // 注意这一步！！每一次都要还原为p，因为双重循环里面的局面都是同一层的
 51 
 52                     if (t.cur[i] < bottle[j] - t.cur[j])    // 可以把cur[i]全部倒入cur[j]    
 53                     {
 54                         t.cur[j] += t.cur[i];
 55                         t.cur[i] = 0;
 56                     }
 57                     else    // 把cur[i]中的水全部倒入cur[j]后，cur[i]还有剩余
 58                     {
 59                         t.cur[i] -= bottle[j] - t.cur[j];
 60                         t.cur[j] = bottle[j];
 61                     }
 62 
 63                     if (!vis[t.cur[0]][t.cur[1]][t.cur[2]])        // 如果这种局面没有出现过
 64                     {
 65                         vis[t.cur[0]][t.cur[1]][t.cur[2]] = 1;
 66                         t.step = p.step + 1;    // 置为p的下一层
 67                         Q.push(t);    // 将其入队
 68                     }
 69                 }
 70 
 71             }
 72         }
 73     }
 74 
 75     cout << "NO" << endl;
 76 
 77 }
 78 
 79 
 80 int main()
 81 {
 82     while (cin >> bottle[0] >> bottle[1] >> bottle[2])
 83     {
 84         if (bottle[0] == 0 && bottle[1] == 0 && bottle[2] == 0)
 85             break;
 86 
 87         if ((bottle[0] & 1) == 1)    // 买的可乐体积是奇数，则不能平分
 88         {
 89             cout << "NO" << endl;
 90             continue;
 91         }
 92 
 93         memset(vis, 0, sizeof(vis));
 94         half = bottle[0] / 2;
 95 
 96         bfs();
 97     }
 98 
 99     return 0;
100 }