直接上中文

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

  1. 3 5 4

Sample Output

  1. 6
  2. FILL(2)
  3. POUR(2,1)
  4. DROP(1)
  5. POUR(2,1)
  6. FILL(2)
  7. POUR(2,1)

题目链接：

https://vjudge.net/problem/POJ-3414

bfs优先队列就OK了，分6种情况讨论入队，具体题解都在代码上，注意看注释

  1. #include <iostream>
  2. #include <cstdio>
  3. #include <fstream>
  4. #include <algorithm>
  5. #include <cmath>
  6. #include <deque>
  7. #include <vector>
  8. #include <queue>
  9. #include <string>
  10. #include <cstring>
  11. #include <map>
  12. #include <stack>
  13. #include <set>
  14. #include <sstream>
  15. #define mod 1000000007
  16. #define eps 1e-6
  17. #define ll long long
  18. #define INF 0x3f3f3f3f
  19. #define ME0(x) memset(x,0,sizeof(x))
  20. using namespace std;
  21. int a,b,c;
  22. int flag=0;//初始化不能成功
  23. int total=0;//总共操作了几次，也是每个操作步骤的下标
  24. int id[105*105];//保存正确路径的下标
  25. int vis[105][105];//标记状态是否入队过
  26. char op[][10]={"0","FILL(1)","FILL(2)", "DROP(1)","DROP(2)","POUR(1,2)","POUR(2,1)"};//最后的输出
  27. struct node
  28. {
  29.     int no;//当前下标
  30.     int k1,k2;//杯中剩余的水
  31.     int op;//操作
  32.     int step;//步数
  33.     int pre;//前一步的下标
  34.     bool operator<(const node &c)const//步数小的先出队
  35.     {
  36.         return step>c.step;
  37.     }
  38. };
  39. priority_queue<node>q;
  40. node now,next;
  41. vector<node> v;
  42. void print(int i)//输出格式
  43. {
  44.     int j=0;
  45.     while(v[i].no)
  46.     {
  47.         id[j++]=v[i].no;//储存正确路径的下标
  48.         i=v[i].pre;
  49.     }
  50.     for(i=j-1; i>=0; i--)//按照下标输出操作
  51.     {
  52.         cout<<op[v[id[i]].op]<<endl;
  53.     }
  54. }
  55. void bfs()
  56. {
  57.     now.k1=0,now.k2=0,now.op=0,now.pre=0,now.step=0,now.no=0;
  58.     vis[now.k1][now.k2]=1;
  59.     q.push(now);
  60.     v.push_back(now);
  61.     while(!q.empty())
  62.     {
  63.         now=q.top();
  64.         q.pop();
  65.         if(now.k1==c||now.k2==c)//满足条件
  66.         {
  67.             flag=1;
  68.             cout<<now.step<<endl;//输出步数
  69.             print(now.no);//输出格式
  70.             break;
  71.         }
  72.         for(int i=1; i<=6; i++)
  73.         {
  74.             if(i == 1) //fill(1)
  75.             {
  76.                 next.k1 = a;
  77.                 next.k2 = now.k2;
  78.             }
  79.             else if(i == 2) //fill(2)
  80.             {
  81.                 next.k1 = now.k1;
  82.                 next.k2 = b;
  83.             }
  84.             else if(i == 3) //drop(1)
  85.             {
  86.                 next.k1 = 0;
  87.                 next.k2 = now.k2;
  88.             }
  89.             else if(i == 4) // drop(2);
  90.             {
  91.                 next.k1 = now.k1;
  92.                 next.k2 = 0;
  93.             }
  94.             else if(i == 5) //pour(1,2)
  95.             {
  96.                 if(now.k1+now.k2 <= b) //如果不能够装满 b
  97.                 {
  98.                     next.k1 = 0;
  99.                     next.k2 = now.k1+now.k2;
  100.                 }
  101.                 else //如果能够装满 b
  102.                 {
  103.                     next.k1 = now.k1+now.k2-b;
  104.                     next.k2 = b;
  105.                 }
  106.             }
  107.             else if(i == 6) // pour(2,1)
  108.             {
  109.                 if(now.k1+now.k2 <= a) //如果不能够装满 a
  110.                 {
  111.                     next.k1 = now.k1+now.k2;
  112.                     next.k2 = 0;
  113.                 }
  114.                 else //如果能够装满 b
  115.                 {
  116.                     next.k1 = a;
  117.                     next.k2 = now.k1+now.k2-a;
  118.                 }
  119.             }
  120.             next.op=i;
  121.             if(!vis[next.k1][next.k2])
  122.             {
  123.                 total++;
  124.                 next.no=total;
  125.                 vis[next.k1][next.k2]=1;
  126.                 next.step=now.step+1;
  127.                 next.pre=now.no;
  128.                 v.push_back(next);
  129.                 q.push(next);
  130.             }
  131.         }
  132.     }
  133.     if(flag==0)
  134.         cout<<"impossible"<<endl;
  135. }
  137. int main()
  138. {
  139.     ME0(vis);
  140.     cin>>a>>b>>c;
  141.     bfs();
  142. }

 

posted on 2019-07-01 17:46 Sky丨Star 阅读(…) 评论(…) 编辑 收藏

版权声明：本文为sky-stars原创文章，遵循 CC 4.0 BY-SA 版权协议，转载请附上原文出处链接和本声明。
本文链接：https://www.cnblogs.com/sky-stars/p/11115635.html