HDOJ_ACM_非常可乐

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

NO
3

Code

View Code

 1 #include <stdio.h>
 2 #include <queue>
 3 using namespace std;
 4 struct State
 5 {
 6     int v[3];
 7     int step; //because this step of pre and cur are maybe the same
 8 };
 9 int volume[3];
10 int BFS()
11 {
12     int map[105][105] = {0};  //initialize and for mark
13     queue<State> q;
14     State cur, pre;
15     int i, j;
16     //initialize the node and push it into the queue
17     cur.v[0] = volume[0];
18     cur.v[1] = 0;
19     cur.v[2] = 0;
20     cur.step = 0;
21     q.push(cur);
22     map[0][0] = 1;
23     while (!q.empty())
24     {
25         pre = q.front();
26         q.pop();
27         //printf("\nstep = %d\n", pre.step);
28         //printf("pre: %d %d %d\n", pre.v[0], pre.v[1], pre.v[2]);
29         /*
30         v[i] -> v[j], when v[i] have water
31         we should consider that when u pull water from v[i] to v[j], v[j] maybe will arive the volume
32         */
33         for (i = 0; i < 3 && pre.v[i] > 0; i++)
34         {
35             for (j = 0; j < 3; j++)
36             {
37                 if (i != j)
38                 {
39                     cur = pre;
40                     cur.step = pre.step + 1;
41                     //when v[j] arrive its volume
42                     if (cur.v[i] + cur.v[j] < volume[j])
43                     {
44                         cur.v[j] = cur.v[i] + cur.v[j];
45                         cur.v[i] = 0;
46                     }
47                     else
48                     {
49                         cur.v[i] = cur.v[i] - (volume[j] - cur.v[j]);
50                         cur.v[j] = volume[j];
51                     }
52                     //judge whether u have traversed the state
53                     if (map[cur.v[1]][cur.v[2]] == 0)
54                     {
55                         if (cur.v[0] == volume[0] / 2 && cur.v[1] == volume[0] / 2)
56                             return cur.step;
57                         q.push(cur);
58                         //printf("cur: %d %d %d\n", cur.v[0], cur.v[1], cur.v[2]);
59                         map[cur.v[1]][cur.v[2]] = 1;
60                     }
61                 }
62             }
63         }
64     }
65     return 0;
66 }
67 int main()
68 {
69     int result;
70     while (scanf("%d %d %d", &volume[0], &volume[1], &volume[2]) != EOF && (volume[0] || volume[1] || volume[2]))
71     {
72         if (volume[1] < volume[2])
73         {
74             int temp = volume[1];
75             volume[1] = volume[2];
76             volume[2] = temp; 
77         }
78         result = BFS();
79         if (volume[0] % 2 != 0)
80             puts("NO");
81         else if (result == 0)
82             puts("NO");
83         else
84             printf("%d\n", BFS());
85     }
86     return 0;
87 }

Idea

Firstly, I use the "辗转相除", it's no doubt that I am wrong. We can use BFS to solve this question. Well, this is still other question that it's hard to describe the translation of state. Maybe u can write one by one, but I find that we can use the struct including v[3] to solve this complicated question. Well, next pic show the every step.

Recommend