poj 3414 pots (bfs+路径记录)
好爽,一遍ac
1
2
3 /*************************************************************************
4 > File Name: code/2015summer/searching/H.cpp
5 > Author: 111qqz
6 > Email: rkz2013@126.com
7 > Created Time: 2015年07月27日 星期一 09时11分28秒
8 ************************************************************************/
9
10 #include<iostream>
11 #include<iomanip>
12 #include<cstdio>
13 #include<algorithm>
14 #include<cmath>
15 #include<cstring>
16 #include<string>
17 #include<map>
18 #include<set>
19 #include<queue>
20 #include<vector>
21 #include<stack>
22 #define y0 abc111qqz
23 #define y1 hust111qqz
24 #define yn hez111qqz
25 #define j1 cute111qqz
26 #define tm crazy111qqz
27 #define lr dying111qqz
28 using namespace std;
29 #define REP(i, n) for (int i=0;i<int(n);++i)
30 typedef long long LL;
31 typedef unsigned long long ULL;
32 const int N=1E2+5;
33 int A,B,C;
34 int d[N][N];
35 bool flag;
36 struct node
37 {
38 int d,opt,par,prea,preb;
39 }q[N][N];
40
41 void print(int x,int y)
42 {
43 // cout<<"x:"<<x<<"y:"<<y<<endl;
44 if (q[x][y].prea!=-1&&q[x][y].preb!=-1)
45 {
46 // cout<<"who is 111qqz"<<endl;
47 print(q[x][y].prea,q[x][y].preb);
48 if (q[x][y].opt==1){
49 printf("FILL(%d)\n",q[x][y].par);
50 }
51 if (q[x][y].opt==2)
52 {
53 printf("DROP(%d)\n",q[x][y].par);
54 }
55 if (q[x][y].opt==3)
56 {
57 printf("POUR(%d,%d)\n",q[x][y].par,3-q[x][y].par);
58 }
59 }
60
61 }
62 void bfs()
63 {
64 memset(q,-1,sizeof(q));
65 queue<int>a;
66 queue<int>b;
67 a.push(0);
68 b.push(0);
69 q[0][0].d=0;
70 while (!a.empty()&&!b.empty())
71 {
72 int av = a.front();a.pop();
73 int bv = b.front();b.pop();
74 // cout<<"av:"<<av<<"bv:"<<bv<<endl;
75 if (av==C||bv==C)
76 {
77 flag = true;
78 //cout<<"yeah~~~~~~~~~~~~~~~"<<endl;
79 cout<<q[av][bv].d<<endl;
80 // cout<<"prea:"<<q[av][bv].prea<<"preb:"<<q[av][bv].preb<<endl;
81 print(av,bv);
82 return;
83 }
84 if (av<A&&q[A][bv].d==-1)
85 {
86 q[A][bv].d=q[av][bv].d+1;
87 q[A][bv].opt=1;
88 q[A][bv].par=1;
89 q[A][bv].prea=av;
90 q[A][bv].preb=bv;
91 a.push(A);
92 b.push(bv);
93 }
94 if (av>0&&q[0][bv].d==-1)
95 {
96 q[0][bv].d=q[av][bv].d+1;
97 q[0][bv].opt=2;
98 q[0][bv].par=1;
99 q[0][bv].prea=av;
100 q[0][bv].preb=bv;
101 a.push(0);
102 b.push(bv);
103
104 }
105 if (bv<B&&q[av][B].d==-1)
106 {
107 q[av][B].d=q[av][bv].d+1;
108 q[av][B].opt=1;
109 q[av][B].par=2;
110 q[av][B].prea = av;
111 q[av][B].preb = bv;
112 a.push(av);
113 b.push(B);
114
115 }
116 if (bv>0&&q[av][0].d==-1)
117 {
118 q[av][0].d=q[av][bv].d+1;
119 q[av][0].opt=2;
120 q[av][0].par=2;
121 q[av][0].prea=av;
122 q[av][0].preb=bv;
123 a.push(av);
124 b.push(0);
125 }
126
127 if (av+bv<=B&&q[0][av+bv].d==-1)
128 {
129 q[0][av+bv].d=q[av][bv].d+1;
130 q[0][av+bv].opt=3;
131 q[0][av+bv].par=1;
132 q[0][av+bv].prea=av;
133 q[0][av+bv].preb=bv;
134 a.push(0);
135 b.push(av+bv);
136 }
137 if (av+bv>B&&q[av-(B-bv)][B].d==-1) //把1往2里倒入的两种情况
138 {
139
140 int tmp = av-(B-bv);
141 q[tmp][B].d=q[av][bv].d+1;
142 q[tmp][B].opt=3;
143 q[tmp][B].par=1;
144 q[tmp][B].prea=av;
145 q[tmp][B].preb=bv;
146 a.push(tmp);
147 b.push(B);
148 }
149
150 if (bv+av<=A&&q[av+bv][0].d==-1)
151 {
152 q[av+bv][0].d=q[av][bv].d+1;
153 q[av+bv][0].opt=3;
154 q[av+bv][0].par=2;
155 q[av+bv][0].prea=av;
156 q[av+bv][0].preb=bv;
157 a.push(av+bv);
158 b.push(0);
159 }
160 if (bv+av>A&&q[A][bv-(A-av)].d==-1)
161 {
162 int tmp = bv-(A-av);
163 q[A][tmp].d=q[av][bv].d+1;
164 q[A][tmp].opt=3;
165 q[A][tmp].par=2;
166 q[A][tmp].prea=av;
167 q[A][tmp].preb=bv;
168 a.push(A);
169 b.push(tmp);
170 }
171 }
172 }
173 int main()
174 {
175
176 flag = false;
177 cin>>A>>B>>C;
178 bfs();
179 if (!flag)
180 {
181 cout<<"impossible"<<endl;
182 }
183
184
185 return 0;
186 }
187
188
189
190