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