Posted on 2008-03-12 18:53
superman 閱讀(658)
評論(0) 編輯 收藏 引用 所屬分類:
ZOJ
1 /* Accepted 1005 C++ 00:00.01 2836K */
2 #include <stdio.h>
3 #include <string.h>
4 #include <iostream>
5
6 using namespace std;
7
8 int min(int a, int b)
9 {
10 return a < b ? a : b;
11 }
12
13 struct
14 {
15 int a, b, last, operation;
16 }queue[65535];
17 int front, rear;
18 bool isRepeat[1001][1001];
19
20 void outPut(int i)
21 {
22 if(i == 0)
23 return;
24 outPut(queue[i].last);
25 switch(queue[i].operation)
26 {
27 case 1 : cout << "fill A" << endl; break;
28 case 2 : cout << "fill B" << endl; break;
29 case 3 : cout << "empty A" << endl; break;
30 case 4 : cout << "empty B" << endl; break;
31 case 5 : cout << "pour A B" << endl; break;
32 case 6 : cout << "pour B A" << endl; break;
33 }
34 }
35
36 int main()
37 {
38 //freopen("p1005.in", "r", stdin);
39
40 int A, B, N;
41
42 while(cin >> A >> B >> N)
43 {
44 memset(isRepeat, 0, sizeof(isRepeat));
45 front = -1, rear = 0;
46 queue[0].a = queue[0].b = 0;
47 queue[0].last = queue[0].operation = 0;
48 while(front < rear)
49 {
50 front++;
51 int a = queue[front].a;
52 int b = queue[front].b;
53
54 if(b == N)
55 {
56 outPut(front);
57 cout << "success" << endl;
58 break;
59 }
60
61 //fill A
62 if(a != A)
63 {
64 rear++;
65 queue[rear].a = A;
66 queue[rear].b = b;
67 queue[rear].last = front;
68 queue[rear].operation = 1;
69 if(isRepeat[queue[rear].a][queue[rear].b])
70 rear--;
71 else
72 isRepeat[queue[rear].a][queue[rear].b] = true;
73 }
74
75 //fill B
76 if(b != B)
77 {
78 rear++;
79 queue[rear].a = a;
80 queue[rear].b = B;
81 queue[rear].last = front;
82 queue[rear].operation = 2;
83 if(isRepeat[queue[rear].a][queue[rear].b])
84 rear--;
85 else
86 isRepeat[queue[rear].a][queue[rear].b] = true;
87 }
88
89 //empty A
90 if(a != 0)
91 {
92 rear++;
93 queue[rear].a = 0;
94 queue[rear].b = b;
95 queue[rear].last = front;
96 queue[rear].operation = 3;
97 if(isRepeat[queue[rear].a][queue[rear].b])
98 rear--;
99 else
100 isRepeat[queue[rear].a][queue[rear].b] = true;
101 }
102
103 //empty B
104 if(b != 0)
105 {
106 rear++;
107 queue[rear].a = a;
108 queue[rear].b = 0;
109 queue[rear].last = front;
110 queue[rear].operation = 4;
111 if(isRepeat[queue[rear].a][queue[rear].b])
112 rear--;
113 else
114 isRepeat[queue[rear].a][queue[rear].b] = true;
115 }
116
117 //pour A to B
118 rear++;
119 queue[rear].a = a - min(a, B - b);
120 queue[rear].b = b + min(a, B - b);
121 queue[rear].last = front;
122 queue[rear].operation = 5;
123 if(isRepeat[queue[rear].a][queue[rear].b])
124 rear--;
125 else
126 isRepeat[queue[rear].a][queue[rear].b] = true;
127
128 //pour B to A
129 rear++;
130 queue[rear].a = a + min(b, A - a);
131 queue[rear].b = b - min(b, A - a);
132 queue[rear].last = front;
133 queue[rear].operation = 6;
134 if(isRepeat[queue[rear].a][queue[rear].b])
135 rear--;
136 else
137 isRepeat[queue[rear].a][queue[rear].b] = true;
138 }
139 }
140
141 return 0;
142 }
143
144