Pots
直接上中文
Descriptions:
给你两个容器，分别能装下A升水和B升水，并且可以进行以下操作
FILL(i) 将第i个容器从水龙头里装满(1 ≤ i ≤ 2);
DROP(i) 将第i个容器抽干
POUR(i,j) 将第i个容器里的水倒入第j个容器（这次操作结束后产生两种结果，一是第j个容器倒满并且第i个容器依旧有剩余，二是第i个容器里的水全部倒入j中，第i个容器为空）
现在要求你写一个程序，来找出能使其中任何一个容器里的水恰好有C升，找出最少操作数并给出操作过程
Input
有且只有一行，包含3个数A,B,C（1<=A,B<=100,C<=max(A,B)）
Output
第一行包含一个数表示最小操作数K
随后K行每行给出一次具体操作，如果有多种答案符合最小操作数，输出他们中的任意一种操作过程，如果你不能使两个容器中的任意一个满足恰好C升的话，输出“impossible”
Sample Input
Sample Output
题目链接：
https://vjudge.net/problem/POJ-3414
bfs优先队列就OK了，分6种情况讨论入队，具体题解都在代码上，注意看注释
#include <iostream>
#include <cstdio>
#include <fstream>
#include <algorithm>
#include <cmath>
#include <deque>
#include <vector>
#include <queue>
#include <string>
#include <cstring>
#include <map>
#include <stack>
#include <set>
#include <sstream>
#define mod 1000000007
#define eps 1e-6
#define ll long long
#define INF 0x3f3f3f3f
#define ME0(x) memset(x,0,sizeof(x))
using namespace std;
int a,b,c;
int flag=;//初始化不能成功
int total=;//总共操作了几次，也是每个操作步骤的下标
int id[*];//保存正确路径的下标
int vis[][];//标记状态是否入队过
char op[][]={"","FILL(1)","FILL(2)", "DROP(1)","DROP(2)","POUR(1,2)","POUR(2,1)"};//最后的输出
struct node
{
int no;//当前下标
int k1,k2;//杯中剩余的水
int op;//操作
int step;//步数
int pre;//前一步的下标
bool operator<(const node &c)const//步数小的先出队
{
return step>c.step;
}
};
priority_queue<node>q;
node now,next;
vector<node> v;
void print(int i)//输出格式
{
int j=;
while(v[i].no)
{
id[j++]=v[i].no;//储存正确路径的下标
i=v[i].pre;
}
for(i=j-; i>=; i--)//按照下标输出操作
{
cout<<op[v[id[i]].op]<<endl;
}
}
void bfs()
{
now.k1=,now.k2=,now.op=,now.pre=,now.step=,now.no=;
vis[now.k1][now.k2]=;
q.push(now);
v.push_back(now);
while(!q.empty())
{
now=q.top();
q.pop();
if(now.k1==c||now.k2==c)//满足条件
{
flag=;
cout<<now.step<<endl;//输出步数
print(now.no);//输出格式
break;
}
for(int i=; i<=; i++)
{
if(i == ) //fill(1)
{
next.k1 = a;
next.k2 = now.k2;
}
else if(i == ) //fill(2)
{
next.k1 = now.k1;
next.k2 = b;
}
else if(i == ) //drop(1)
{
next.k1 = ;
next.k2 = now.k2;
}
else if(i == ) // drop(2);
{
next.k1 = now.k1;
next.k2 = ;
}
else if(i == ) //pour(1,2)
{
if(now.k1+now.k2 <= b) //如果不能够装满 b
{
next.k1 = ;
next.k2 = now.k1+now.k2;
}
else //如果能够装满 b
{
next.k1 = now.k1+now.k2-b;
next.k2 = b;
}
}
else if(i == ) // pour(2,1)
{
if(now.k1+now.k2 <= a) //如果不能够装满 a
{
next.k1 = now.k1+now.k2;
next.k2 = ;
}
else //如果能够装满 b
{
next.k1 = a;
next.k2 = now.k1+now.k2-a;
}
}
next.op=i;
if(!vis[next.k1][next.k2])
{
total++;
next.no=total;
vis[next.k1][next.k2]=;
next.step=now.step+;
next.pre=now.no;
v.push_back(next);
q.push(next);
}
}
}
if(flag==)
cout<<"impossible"<<endl;
} int main()
{
ME0(vis);
cin>>a>>b>>c;
bfs();
}