题意:
已知两个空桶的容量,有三种操作。
1.把桶加满
2.把桶倒空
3.把A中的水尽可能多得加到B中
问最少操作多少次,使任意一个桶中的水达到 C
分析:
一个桶有三种操作,也就是 一个桶可以演变出三种状态,两个桶就是有六种状态。
可以用BFS,把每一种状态加入到一个优先队列中,优先队列按照操作步数升序维护。
每次取优先队列的第一个状态,去判断它所能达到的六种状态!!!
再用一个vis数字标记某一组状态是否出现过,如果没有出现过就加入到队列,
如果出现过,不需要加入,继续判断之后的状态。
如果所有的状态都出现了,并且优先队列为空了,那么就是“impossible”,
如果其中一个队列满足要求,这时就需要输入路径,,,
-----路径的输出-----
每一个状态维护一个到达这个状态所进行的操作顺序,
这样,当到终点的时候,就能直接输出路径
详细请看代码:
代码:
#include <iostream>
#include <queue>
using namespace std;
const int MAXN = 110;
int A, B, C;
int vis[MAXN][MAXN];
string path[MAXN] = {"FILL(1)","FILL(2)",
"DROP(1)","DROP(2)",
"POUR(1,2)","POUR(2,1)"};队列
struct Node
{
int a, b, step;
queue<int>p;
} t, nx;
struct cmp
{
bool operator ()(Node &a, Node &b)
{
return a.step > b.step;
}
};
priority_queue<Node, vector<Node>, cmp> q;
void BFS()
{
t.a = 0, t.b = 0, t.step = 0;
vis[0][0] = 1;
q.push(t);
while(!q.empty())
{
t = q.top();
q.pop();
nx.step = t.step + 1;
for (int i = 0; i < 6; i++)
{
if (i == 0 && t.a != A) { //填满A
nx.a = A;
nx.b = t.b;
nx.p=t.p;
nx.p.push(0);
} else if(i == 1 && t.b != B) { //填满B
nx.b = B;
nx.a = t.a;
nx.p=t.p;
nx.p.push(1);
} else if (i == 2 && t.a != 0){ //抽干A
nx.a = 0;
nx.b = t.b;
nx.p=t.p;
nx.p.push(2);
} else if (i == 3 && t.b != 0){ //抽干B
nx.a = t.a;
nx.b = 0;
nx.p=t.p;
nx.p.push(3);
}else if(i==4&&t.a!=0&&t.b!=B){ //A->B
if (t.a+t.b > B)
nx.b=B, nx.a=t.a+t.b-B;
else
nx.a=0, nx.b=t.a+t.b;
nx.p=t.p;
nx.p.push(4);
} else if(i==5&&t.a!=A&&t.b!=0){//B->A
if (t.a+t.b > A)
nx.a = A, nx.b = t.a+t.b-A;
else
nx.b = 0, nx.a = t.a+t.b;
nx.p=t.p;
nx.p.push(5);
}else
continue;
// -------
if (vis[nx.a][nx.b]) continue;
//cout << nx.a <<" "<<nx.b<<" "<<nx.step<< endl;
if (nx.a == C || nx.b == C)
{
cout << nx.step << endl;
while (!nx.p.empty()) {
cout << path[nx.p.front()] << endl;
nx.p.pop();
}
return;
}
vis[nx.a][nx.b] = 1;
q.push(nx);
}
}
cout << "impossible" << endl;
return ;
}
int main()
{
cin >> A >> B >> C;
BFS();
return 0;
}
Comments | NOTHING