POJ 3414 Pots

　　题意：有两个杯子容量分别为 A,B；每次可以将其中一杯杯子倒满或倒空，或者将一个杯子中的水倒入另外一个杯子（必须将其中一个杯子倒空或倒满）。
　　这样每种状态就有可能衍生出六种新的状态。
　　典型的BFS。
  1 #include <iostream>
  2 #include <cstdio>
  3 #include <cstring>
  4 #include <cstdlib>
  5 #include <queue>
  6 #include <vector>
  7 
  8 using namespace std;
  9 
 10 int n,m;
 11 
 12 bool sta[110][110];
 13 
 14 struct Q
 15 {
 16     int n,m,step,mark,pre;
 17 } t,nt;
 18 
 19 Q q[100010];
 20 
 21 vector<int> s;
 22 
 23 void output_path(int i)
 24 {
 25     if(i == 0)
 26         return ;
 27 
 28     s.push_back(q[i].mark);
 29 
 30     while(q[i].pre)
 31     {
 32         i = q[i].pre;
 33         s.push_back(q[i].mark);
 34     }
 35 
 36     for(i = s.size()-1; i>= 0 ; --i)
 37     {
 38         switch(s[i])
 39         {
 40         case 1 :
 41             printf("DROP(1)
");
 42             break;
 43         case 2 :
 44             printf("DROP(2)
");
 45             break;
 46         case 3 :
 47             printf("FILL(1)
");
 48             break;
 49         case 4 :
 50             printf("FILL(2)
");
 51             break;
 52         case 5 :
 53             printf("POUR(1,2)
");
 54             break;
 55         case 6 :
 56             printf("POUR(2,1)
");
 57             break;
 58         default :
 59             break;
 60         }
 61     }
 62 
 63 }
 64 
 65 void bfs(int n,int m,int k)
 66 {
 67     t.m = t.n = t.step = t.mark = 0;
 68     int s = 0, e = 1;
 69     q[0] = t;
 70 
 71     sta[0][0] = true;
 72 
 73     while(s != e)
 74     {
 75         t = q[s++];
 76 
 77         if(t.m == k || t.n == k)
 78         {
 79             printf("%d
",t.step);
 80             output_path(s-1);
 81             return ;
 82         }
 83         if(t.n != 0)
 84         {
 85             nt.m = t.m;//dour(1);
 86             nt.n = 0;
 87             if(sta[nt.n][nt.m] == false)
 88             {
 89                 nt.mark = 1;
 90                 nt.step = t.step+1;
 91                 nt.pre = s-1;
 92                 q[e++] = nt;
 93                 sta[nt.n][nt.m] = true;
 94             }
 95         }
 96 
 97         if(t.m != 0)
 98         {
 99             nt.m = 0;//dour(2);
100             nt.n = t.n;
101             if(sta[nt.n][nt.m] == false)
102             {
103                 nt.mark = 2;
104                 nt.step = t.step+1;
105                 nt.pre = s-1;
106                 q[e++] = nt;
107                 sta[nt.n][nt.m] = true;
108             }
109         }
110 
111         if(t.n != n)
112         {
113             nt.m = t.m;//fill(1);
114             nt.n = n;
115             if(sta[nt.n][nt.m] == false)
116             {
117                 nt.mark = 3;
118                 nt.step = t.step+1;
119                 nt.pre = s-1;
120                 q[e++] = nt;
121                 sta[nt.n][nt.m] = true;
122             }
123         }
124 
125 
126         if(t.m != m)
127         {
128             nt.m = m;//fill(2);
129             nt.n = t.n;
130             if(sta[nt.n][nt.m] == false)
131             {
132                 nt.mark = 4;
133                 nt.step = t.step+1;
134                 nt.pre = s-1;
135                 q[e++] = nt;
136                 sta[nt.n][nt.m] = true;
137             }
138         }
139 
140         if(t.n != 0 && t.m != m)
141         {
142             if(t.n > m-t.m)//pour(1,2);
143             {
144                 nt.n = t.n - (m-t.m);
145                 nt.m = m;
146             }
147             else
148             {
149                 nt.n = 0;
150                 nt.m = t.m + t.n;
151             }
152             if(sta[nt.n][nt.m] == false)
153             {
154                 nt.mark = 5;
155                 nt.step = t.step+1;
156                 nt.pre = s-1;
157                 q[e++] = nt;
158                 sta[nt.n][nt.m] = true;
159             }
160         }
161 
162         if(t.m != 0 && t.n != n)
163         {
164             if(t.m > n-t.n)//pour(2,1);
165             {
166                 nt.m = t.m - (n-t.n);
167                 nt.n = n;
168             }
169             else
170             {
171                 nt.m = 0;
172                 nt.n = t.m + t.n;
173             }
174             if(sta[nt.n][nt.m] == false)
175             {
176                 nt.mark = 6;
177                 nt.step = t.step+1;
178                 nt.pre = s-1;
179                 q[e++] = nt;
180                 sta[nt.n][nt.m] = true;
181             }
182         }
183     }
184     printf("impossible
");
185     return ;
186 }
187 
188 int main()
189 {
190     int n,m,k;
191 
192     scanf("%d %d %d",&n,&m,&k);
193 
194     memset(sta,false,sizeof(sta));
195 
196     bfs(n,m,k);
197 
198     return 0;
199 }
View Code