poj3414(Pots)

题目地址：Pots

题目大意：

有两个容量分别为A,B的容器，可以通过以下操作：

FILL(i) 将容器 i （1=<i<=2）装满。
DROP(i) 将容器 i （1=<i<=2）漏空。
POUR(i,j) 将容器i 里的水转移到 j 容器中，可能 i 容器里面的水会有剩余，因为j 容器满了，如果 j 容器有足够的容量储存 i 里面的水，则 i 容器就会倒空。

问你至少通过多少次操作，让其中的一个容器的水容量达到C的大小。

解题思路：

广搜BSF。搜索简单，但是记得记录路径，如果已知终点和起点，这样记录路径的时候可以从终点搜索到达起点，这样就可以正着输出路径，但是这个题不知道终点的状态，所以只能倒着记录路径。倒着记完路径，已经形成了一条路径，然后再正着储存一遍。

EX：

i=path[x][y].x;
j=path[x][y].y;
path1[i][j].x=x;
path1[i][j].y=y;

　这样path1的路径就是正着的，这样利于输出具体什么操作得到的下一个状态。

代码：

  1 #include <algorithm>
  2 #include <iostream>
  3 #include <sstream>
  4 #include <cstdlib>
  5 #include <cstring>
  6 #include <cstdio>
  7 #include <string>
  8 #include <bitset>
  9 #include <vector>
 10 #include <queue>
 11 #include <stack>
 12 #include <cmath>
 13 #include <list>
 14 //#include <map>
 15 #include <set>
 16 using namespace std;
 17 /***************************************/
 18 #define ll long long
 19 #define int64 __int64
 20 #define PI 3.1415927
 21 /***************************************/
 22 const int INF = 0x7f7f7f7f;
 23 const double eps = 1e-8;
 24 const double PIE=acos(-1.0);
 25 const int d1x[]= {0,-1,0,1};
 26 const int d1y[]= {-1,0,1,0};
 27 const int d2x[]= {0,-1,0,1};
 28 const int d2y[]= {1,0,-1,0};
 29 const int fx[]= {-1,-1,-1,0,0,1,1,1};
 30 const int fy[]= {-1,0,1,-1,1,-1,0,1};
 31 const int dirx[]= {-1,1,-2,2,-2,2,-1,1};
 32 const int diry[]= {-2,-2,-1,-1,1,1,2,2};
 33 /*vector <int>map[N];map[a].push_back(b);int len=map[v].size();*/
 34 /***************************************/
 35 void openfile()
 36 {
 37     freopen("data.in","rb",stdin);
 38     freopen("data.out","wb",stdout);
 39 }
 40 priority_queue<int> qi1;
 41 priority_queue<int, vector<int>, greater<int> >qi2;
 42 /**********************华丽丽的分割线,以上为模板部分*****************/
 43 int vis[101][101];
 44 int cnt[101][101];
 45 int ce;
 46 struct Node
 47 {
 48     int x;
 49     int y;
 50 } path[101][101];
 51 Node path1[101][101];
 52 int a,b,c;
 53 int aa,bb;
 54 int BFS(int x,int y)
 55 {
 56     queue<Node >Q;
 57     Node node;
 58     node.x=x;
 59     node.y=y;
 60     Q.push(node);
 61     while(!Q.empty())
 62     {
 63         Node v=Q.front();
 64         Q.pop();
 65         int xx=v.x;
 66         int yy=v.y;
 67 
 68         vis[xx][yy]=1;
 69         if (xx==c||yy==c)
 70         {
 71             ce=cnt[xx][yy];
 72             aa=xx;
 73             bb=yy;
 74             return 0;
 75         }
 76         //fill(a);
 77         xx=a;
 78         yy=v.y;
 79         if (!vis[xx][yy])
 80         {
 81             node.x=xx;
 82             node.y=yy;
 83             Q.push(node);
 84             vis[xx][yy]=1;
 85             cnt[xx][yy]=cnt[v.x][v.y]+1;
 86             path[xx][yy].x=v.x;
 87             path[xx][yy].y=v.y;
 88         }
 89         //fill(b);
 90         xx=v.x;
 91         yy=b;
 92         if (!vis[xx][yy])
 93         {
 94             node.x=xx;
 95             node.y=yy;
 96             Q.push(node);
 97             vis[xx][yy]=1;
 98             cnt[xx][yy]=cnt[v.x][v.y]+1;
 99             path[xx][yy].x=v.x;
100             path[xx][yy].y=v.y;
101         }
102         //drop(a);
103         xx=0;
104         yy=v.y;
105         if (!vis[xx][yy])
106         {
107             node.x=xx;
108             node.y=yy;
109             Q.push(node);
110             vis[xx][yy]=1;
111             cnt[xx][yy]=cnt[v.x][v.y]+1;
112             path[xx][yy].x=v.x;
113             path[xx][yy].y=v.y;
114         }
115         //drop(b);
116         xx=v.x;
117         yy=0;
118         if (!vis[xx][yy])
119         {
120             node.x=xx;
121             node.y=yy;
122             Q.push(node);
123             vis[xx][yy]=1;
124             cnt[xx][yy]=cnt[v.x][v.y]+1;
125             path[xx][yy].x=v.x;
126             path[xx][yy].y=v.y;
127         }
128         //pour(a,b);
129         int yu=b-v.y;
130         if (yu>=v.x)
131         {
132             xx=0;
133             yy=v.y+v.x;
134         }
135         else
136         {
137             yy=b;
138             xx=v.x-yu;
139         }
140         if (!vis[xx][yy])
141         {
142             node.x=xx;
143             node.y=yy;
144             Q.push(node);
145             vis[xx][yy]=1;
146             cnt[xx][yy]=cnt[v.x][v.y]+1;
147             path[xx][yy].x=v.x;
148             path[xx][yy].y=v.y;
149         }
150         //pour(b,a);
151         yu=a-v.x;
152         if (yu>=v.y)
153         {
154             xx=v.x+v.y;
155             yy=0;
156         }
157         else
158         {
159             xx=a;
160             yy=v.y-yu;
161         }
162         if (!vis[xx][yy])
163         {
164             node.x=xx;
165             node.y=yy;
166             Q.push(node);
167             vis[xx][yy]=1;
168             cnt[xx][yy]=cnt[v.x][v.y]+1;
169             path[xx][yy].x=v.x;
170             path[xx][yy].y=v.y;
171         }
172     }
173 }
174 int main()
175 {
176     while(scanf("%d%d%d",&a,&b,&c)!=EOF)
177     {
178         ce=-1;
179         int max=a;
180         int i,j;
181         memset(vis,0,sizeof(vis));
182         memset(cnt,0,sizeof(cnt));
183         memset(path,0,sizeof(path));
184         memset(path1,0,sizeof(path1));
185         if (a<b)
186             max=b;
187         BFS(0,0);
188         int x=-1,y=-1;
189         if (ce!=-1)
190         {
191             printf("%d
",ce);
192             x=aa;
193             y=bb;
194             int dd=0;
195             while(1)
196             {
197                 i=path[x][y].x;
198                 j=path[x][y].y;
199                 path1[i][j].x=x;
200                 path1[i][j].y=y;
201                 dd++;
202                 x=i;
203                 y=j;
204                 if (dd==ce)
205                     break;
206             }
207             x=0;
208             y=0;
209             dd=0;
210             while(1)
211             {
212                 i=path1[x][y].x;
213                 j=path1[x][y].y;
214                 int xx=x;
215                 int yy=y;
216                 //fill(a);
217                 xx=a;
218                 yy=y;
219                 if(xx==i&&yy==j)
220                     printf("FILL(1)
");
221                 //fill(a);
222                 xx=x;
223                 yy=b;
224                 if(xx==i&&yy==j)
225                     printf("FILL(2)
");
226                 //drop(a);
227                 xx=0;
228                 yy=y;
229                 if(xx==i&&yy==j)
230                     printf("DROP(1)
");
231                 //drop(b);
232                 xx=x;
233                 yy=0;
234                 if(xx==i&&yy==j)
235                     printf("DROP(2)
");                //pour(a,b);
236                 int yu=b-y;
237                 if (yu>=x)
238                 {
239                     xx=0;
240                     yy=y+x;
241                 }
242                 else
243                 {
244                     yy=b;
245                     xx=x-yu;
246                 }
247                 if(xx==i&&yy==j)
248                     printf("POUR(1,2)
");
249                 //pour(b,a);
250                 yu=a-x;
251                 if (yu>=y)
252                 {
253                     xx=x+y;
254                     yy=0;
255                 }
256                 else
257                 {
258                     xx=a;
259                     yy=y-yu;
260                 }
261                 if(xx==i&&yy==j)
262                     printf("POUR(2,1)
");
263                 x=i;
264                 y=j;
265                 dd++;
266                 if (dd==ce)
267                     break;
268             }
269         }
270         else
271             printf("impossible
");
272     }
273     return 0;
274 }

View Code