<题目链接>
题目大意：
有两个容量的空杯子，能够对这两个空杯子进行三种操作：
分别是fill(a)，装满a杯子；
drop(a)，倒空a杯子；
pour(a,b)，将a杯子中的水倒入b杯子中；
现在问你，是否能够通过这三种操作，使得这两个杯子中至少有一个杯子中含有c体积的水，如果不行，输出“impossible”，如果可以，输出操作的步数，以及每一步的具体操作。
解题分析：
此题与一道输出路径的很相像，只不过那道题是输出每一次操作对应的点的状态，而此题是要输出具体的操作。不难想到，我们依然可以记录下BFS路径上点的状态，然后根据这个点和上一个点的状态差距推导出它们之间的具体操作。
#include <cstdio>
#include <cstring> int v[],m; const int maxn=;
int vis[][];
int flag; struct node{
int val[];
int step;
int pre; //记录上一个点在que[]数组中的位置
node(int a=,int b=,int c=,int d=-){
val[]=a,val[]=b,step=c,pre=d;
}
}que[maxn]; void fill(node &now,int a){
now.val[a]=v[a];
} void drop(node &now,int a){
now.val[a]=;
} void pour(node &now,int a,int b){
int sum=now.val[a]+now.val[b];
if(sum>v[b]){
now.val[b]=v[b];
now.val[a]=sum-v[b];
}
else{
now.val[b]=sum;
now.val[a]=;
}
} void print(node tmp){ //根据相邻两个点的状况来推断操作
if(tmp.pre!=-){
print(que[tmp.pre]);
}
if(tmp.pre!=-){ //如果这个点和上一个点之间有操作,就可以将这个操作求出来
node prenode=que[tmp.pre];
node cal=prenode;
pour(cal,,);
if(tmp.val[]==v[]&&tmp.val[]==prenode.val[]){
printf("FILL(1)\n");
}
else if(tmp.val[]==v[]&&tmp.val[]==prenode.val[]){
printf("FILL(2)\n");
}
else if(tmp.val[]==&&tmp.val[]==prenode.val[]){
printf("DROP(1)\n");
}
else if(tmp.val[]==&&tmp.val[]==prenode.val[]){
printf("DROP(2)\n");
}
else if(cal.val[]==tmp.val[]&&cal.val[]==tmp.val[]){
printf("POUR(1,2)\n");
}
else{
printf("POUR(2,1)\n");
}
}
} void bfs(){
memset(vis,,sizeof(vis));
int front=,end=;
vis[][]=;
que[end++]=node(,,,-);
while(front<end){
node now=que[front];
front++;
if(now.val[]==m||now.val[]==m){
flag=true;
printf("%d\n",now.step);
print(now);
return;
}
for(int i=;i<=;i++){ //装满
node tmp=now; //注意，这里为了防止now发生改变，从而对后面的操作产生影响，所以这里是对tmp进行操作
fill(tmp,i);
if(!vis[tmp.val[]][tmp.val[]]){
vis[tmp.val[]][tmp.val[]]=;
que[end++]=node(tmp.val[],tmp.val[],tmp.step+,front-);
}
}
for(int i=;i<=;i++){ //倒空
node tmp=now;
drop(tmp,i);
if(!vis[tmp.val[]][tmp.val[]]){
vis[tmp.val[]][tmp.val[]]=;
que[end++]=node(tmp.val[],tmp.val[],tmp.step+,front-);
}
}
for(int i=;i<=;i++){ //i向j注水
for(int j=;j<=;j++){
if(i==j)continue;
node tmp=now;
pour(tmp,i,j);
if(!vis[tmp.val[]][tmp.val[]]){
vis[tmp.val[]][tmp.val[]]=;
que[end++]=node(tmp.val[],tmp.val[],tmp.step+,front-);
}
}
}
}
} int main(){
while(scanf("%d %d %d",&v[],&v[],&m)!=EOF){
flag=false;
bfs();
if(!flag){
printf("impossible\n");
}
}
return ;
}
2018-08-29