superman

聚精会神搞建设 一心一意谋发展
posts - 190, comments - 17, trackbacks - 0, articles - 0
   :: 首页 :: 新随笔 :: 联系 :: 聚合  :: 管理

ZOJ 1005 - Jugs

Posted on 2008-03-12 18:53 superman 阅读(654) 评论(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, 0sizeof(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 

只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理