Pots(POJ - 3414)
算法
BFS
1.这道题问的是给你两个体积分别为A和B的容器，你对它们有三种操作，一种是装满其中一个瓶子，另一种是把其中一个瓶子的水都倒掉，还有一种就是把其中一个瓶子的水导入另一个瓶子中(可能会有剩余)。最后让你输出在能够得出体积为C的水的情况下操作的最小次数并且把过程输出。如果无法得出体积为C的水，则输出“impossible”。
2.这个题主要涉及两个点，一个是求出最小次数，还有一个就是把路径输出。对于这种有目标值的求最小次数问题，我们可以使用bfs解决。初始状态是两个瓶子都为空，最终状态是其中一个瓶子中的水的容量达到了目标值C。在每个状态下可以对瓶子进行上面描述的三种操作，细分下来其实只有6中操作，分别是：
- 将A瓶子装满水
- 将B瓶子装满水
- 将A瓶子中的水倒入B瓶子中
- 将B瓶子中的倒入A瓶子中
- 将A瓶子中的水全部抽走
- 将B瓶子中的水全部抽走
我们可以把每种状态都放入到队列中，当到达某种状态时，就分别执行上面6个操作，同时需要注意做好每种状态的标记，避免重复。
3.为了获得路径，我们可以把每次将新的状态插入队列中的同时用数组记录，可以用结构体来存放每个状态，该结构体中除了当前A瓶和B瓶中水的容量这两种属性外，还要有它本身在数组中的下标id，父状态在数组中的下标pre，到达此状态时的最小步数steps。由于bfs的特殊性，我们可以认为当达到目标值时的steps为最小最优的(至于为什么是最优的，我们可以简单的想bfs因为是一层一层的搜索的，所以可以认为第一个到达目标值的层数是最小的，当然前提是代价是一样的，比如这里每执行一步都表示一次，故可以用bfs实现，而如果执行每种操作的代价不同，就不能用bfs来实现了)。
C++代码
#include<iostream>
#include<queue>
#include<stack>
#include<cstdio>
using namespace std;
const int N = 1e6 + 10, M = 1e3;
int a, b, c;
bool st[M][M];
struct Status{
int ca, cb, pre;
int ope; //1表示装满A,2表示装满B,3表示A倒入B,4表示B倒入A,5表示倒掉A,6表示倒掉B
int steps;
int id;
Status(){
ca = 0, cb = 0, pre = -1;
ope = -1;
steps = 0;
id = 0;
}
}s[N];
int cnt;
//装满A
void fullA(Status& t)
{
t.ca = a;
t.ope = 1;
t.steps++;
t.id = cnt;
//s[cnt++] = t;
}
//倒掉A
void pourA(Status& t)
{
t.ca = 0;
t.ope = 5;
t.steps++;
t.id = cnt;
//s[cnt++] = t;
}
//装满B
void fullB(Status& t)
{
t.cb = b;
t.ope = 2;
t.steps++;
t.id = cnt;
//s[cnt++] = t;
}
//倒掉B
void pourB(Status& t)
{
t.cb = 0;
t.ope = 6;
t.steps++;
t.id = cnt;
// s[cnt++] = t;
}
//A倒入B
void pourA_B(Status& t)
{
if(t.ca >= b - t.cb)
{
t.ca -= b - t.cb;
t.cb = b;
}
else
{
t.cb += t.ca;
t.ca = 0;
}
t.ope = 3;
t.steps++;
t.id = cnt;
//s[cnt++] = t;
}
//B倒入A
void pourB_A(Status& t)
{
if(t.cb >= a - t.ca)
{
t.cb -= a - t.ca;
t.ca = a;
}
else
{
t.ca += t.cb;
t.cb = 0;
}
t.ope = 4;
t.steps++;
t.id = cnt;
//s[cnt++] = t;
}
void print(Status t)
{
cout << t.steps << endl;
stack<Status> sta;
sta.push(t);
while(true)
{
if(t.pre == -1) break;
t = s[t.pre];
sta.push(t);
}
while(sta.size())
{
Status tmp = sta.top();
sta.pop();
if(tmp.ope == 1)
puts("FILL(1)");
else if(tmp.ope == 2)
puts("FILL(2)");
else if(tmp.ope == 3)
puts("POUR(1,2)");
else if(tmp.ope == 4)
puts("POUR(2,1)");
else if(tmp.ope == 5)
puts("DROP(1)");
else if(tmp.ope == 6)
puts("DROP(2)");
}
}
void bfs()
{
Status tmp;
queue<Status> que;
que.push(tmp);
st[tmp.ca][tmp.cb] = true;
s[cnt++] = tmp;
while(que.size())
{
tmp = que.front();
que.pop();
//cout << "***" << tmp.ca << ", " << tmp.cb << endl;
if(tmp.ca == c || tmp.cb == c)
{
//cout << "**end** " << tmp.ca << " , " << tmp.cb << ", " << tmp.pre << endl;
//打印输出
print(tmp);
return ;
}
//循环那六种情况
for(int i = 1; i <= 6; i++)
{
Status tmp1 = tmp;
//cout << "tmp*** " << tmp.ca << ", " << tmp.cb << endl;
if(i == 1)
{
if(tmp1.ca == a) continue;
fullA(tmp1);
if(!st[tmp1.ca][tmp1.cb])
{
tmp1.pre = tmp.id;
st[tmp1.ca][tmp1.cb] = true;
que.push(tmp1);
s[cnt++] = tmp1;
//cout << "tmp1**1* " << tmp1.ca << ", " << tmp1.cb << endl;
}
}
else if(i == 2)
{
if(tmp1.cb == b) continue;
fullB(tmp1);
if(!st[tmp1.ca][tmp1.cb])
{
tmp1.pre = tmp.id;
st[tmp1.ca][tmp1.cb] = true;
que.push(tmp1);
s[cnt++] = tmp1;
//cout << "tmp1**2* " << tmp1.ca << ", " << tmp1.cb << endl;
}
}
else if(i == 3)
{
if(!(tmp1.ca)) continue;
pourA_B(tmp1);
if(!st[tmp1.ca][tmp1.cb])
{
tmp1.pre = tmp.id;
st[tmp1.ca][tmp1.cb] = true;
que.push(tmp1);
s[cnt++] = tmp1;
//cout << "tmp1**3* " << tmp1.ca << ", " << tmp1.cb << endl;
}
}
else if(i == 4)
{
if(!(tmp1.cb)) continue;
pourB_A(tmp1);
if(!st[tmp1.ca][tmp1.cb])
{
tmp1.pre = tmp.id;
st[tmp1.ca][tmp1.cb] = true;
que.push(tmp1);
s[cnt++] = tmp1;
//cout << "tmp1**4* " << tmp1.ca << ", " << tmp1.cb << endl;
}
}
else if(i == 5)
{
if(!(tmp1.ca)) continue;
pourA(tmp1);
if(!st[tmp1.ca][tmp1.cb])
{
tmp1.pre = tmp.id;
st[tmp1.ca][tmp1.cb] = true;
que.push(tmp1);
s[cnt++] = tmp1;
//cout << "tmp1**5* " << tmp1.ca << ", " << tmp1.cb << endl;
}
}
else if(i == 6)
{
if(!(tmp1.cb)) continue;
pourB(tmp1);
if(!st[tmp1.ca][tmp1.cb])
{
tmp1.pre = tmp.id;
st[tmp1.ca][tmp1.cb] = true;
que.push(tmp1);
s[cnt++] = tmp1;
//cout << "tmp1**6* " << tmp1.ca << ", " << tmp1.cb << endl;
}
}
}
}
puts("impossible");
}
int main()
{
cin >> a >> b >> c;
bfs();
return 0;
}