http://poj.org/problem?id=3414
题意:
给你两个容量为a,b的杯子;有3个操作:
1:FILL(i);把第i个杯子从水库中装满;
2:DROP(i);把第i个杯子清空;
3:POUR(i,j);把第i个杯子的水移入到j中,直到第i个杯子空了或者第j个杯子满了为止;
分析:本题和上篇的差不多,多的就是输出路径;
包含六个过程:水池—>a; 水池—>b;a->水池;b->水池;a->b;b->a;
| prea
pre[x][y] | preb
| op
第一个杯子的水量为x,第二个杯子水量为y它是由第一个水量为pre[x][y].prea、第二个水量为pre[x][y].preb经过操作op来变成的;
最后根据最终两个杯子中水的剩余量把路径倒着存入path中;
代码如下:
#include<stdio.h>
#include<iostream>
#include<string.h>
#include<queue>
#define N 110
using namespace std;
struct node
{
int a,b,step;
friend bool operator< (node a,node b)
{
return a.step>b.step;
}
};
struct NODE
{
int prea,preb,op;
};
NODE pre[N][N];
int a,b,c,flag;
int vis[N][N];
node bfs()
{
int i;
priority_queue<node>Q;
node p,q;
p.a=p.b=;
p.step=;
pre[][].prea=pre[][].prea=pre[][].op=;
memset(vis,,sizeof(vis));
vis[][]=;
Q.push(p);
while(!Q.empty())
{
q=Q.top();
Q.pop();
if(q.a==c||q.b==c)
{
flag=;
return q;
}
for(i=;i<=;i++)
{
if(i==)//FILL(1);
{
p.a=a;
p.b=q.b;
}
if(i==)//FILL(2);
{
p.a=q.a;
p.b=b;
}
if(i==)//DROP(1)
{
p.a=;
p.b=q.b;
}
if(i==)//DROP(2)
{
p.a=q.a;
p.b=;
}
if(i==)//POUR(1,2)
{
if(b-q.b>=q.a)//a倒b中,a倒完了;
{
p.a=;
p.b=q.a+q.b;
}
else
{
p.b=b;
p.a=q.a-(b-q.b);
}
}
if(i==)//POUR(2,1)
{
if(a-q.a>=q.b)//b倒a中,b倒完了;
{
p.b=;
p.a=q.a+q.b;
}
else
{
p.a=a;
p.b=q.b-(a-q.a);
}
}
if(vis[p.a][p.b]==)
{
vis[p.a][p.b]=; p.step=q.step+; pre[p.a][p.b].prea=q.a;
pre[p.a][p.b].preb=q.b;
pre[p.a][p.b].op=i; Q.push(p);
}
} }}int main()
{
node re;
int path[N],i,x,y,step,x1;
while(scanf("%d%d%d",&a,&b,&c)!=EOF)
{
memset(path,,sizeof(path));
flag=;
re=bfs();
if(flag==)
{
printf("impossible\n");
}
else
{
printf("%d\n",re.step);
step=re.step;
x=re.a;
y=re.b;
for(i=step;i>=;i--)//把路径保存在path中;
{
path[i]=pre[x][y].op;
x1=x;
x=pre[x1][y].prea;//更新x,y;
y=pre[x1][y].preb;
}
for(i=;i<=re.step;i++)
{
if(path[i]==)
{
printf("FILL(1)\n");
}
if(path[i]==)
{
printf("FILL(2)\n");
}
if(path[i]==)
{
printf("DROP(1)\n");
}
if(path[i]==)
{
printf("DROP(2)\n");
}
if(path[i]==)
{
printf("POUR(1,2)\n");
}
if(path[i]==)
{
printf("POUR(2,1)\n");
}
}
} }
return ;
}