倒酒问题
来源：http://218.5.5.242:9018/JudgeOnline/problem.php?id=1428
题目描述
分别输入三个杯子容量a，b,c 且第一个为初始杯中的酒量，另外两个为空的。现要求你要精确量出
的e容量的酒。问最少通过几步能精确量出你所要的容量。.例如有三个烧杯容量分别为:80、50、30毫升，现在第一个杯中装满了80
毫升水，其余两个是空的。现要精确的40毫升水，不许用其它工具，请找出最少步骤的方法。 若超过100步，则认为这种计量方法太麻烦
，直接输出“no answer”
样例输入
80 50 30 40
样例输出
step1:30 50 0
step2:30 20 30
step3:60 20 0
step4:60 0 20
step5:10 50 20
step6:10 40 30
代码
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 |
#include<iostream> using namespace std; int n,t=0,w=1,m,ans=0; int d[10000][4],f[10000],h[100]; int a,b,c,e; bool pd(int x,int y,int z,int t) { for(int k=0;k<=w;k++) { if(d[k][1]==x&&d[k][2]==y&&d[k][3]==z) return 0; else continue; } return 1; } void an() { if(d[w][1]==e||d[w][2]==e||d[w][3]==e) { ans=1; int s=w; while(s!=0) { h[d[s][0]]=s; s=f[s]; } for(int i=1;i<=d[w][0];i++) { cout<<"step"<<i<<':'<<d[h[i]][1]<<' '<<d[h[i]][2]<<' '<<d[h[i]][3]<<endl; } } } void search() { d[0][1]=a;d[0][2]=0;d[0][3]=0;d[0][0]=0; while(t<w) { if(ans==1||t>100)return; m=min(d[t][1],b-d[t][2]); if(pd(d[t][1]-m,d[t][2]+m,d[t][3],d[t][0])) {f[++w]=t;d[w][1]=d[t][1]-m; d[w][2]=d[t][2]+m;d[w][3]=d[t][3];d[w][0]=d[t][0]+1;an();}//1>2 m=min(d[t][1],c-d[t][3]); if(pd(d[t][1]-m,d[t][2],d[t][3]+m,d[t][0])) {f[++w]=t;d[w][1]=d[t][1]-m; d[w][2]=d[t][2];d[w][3]=d[t][3]+m;d[w][0]=d[t][0]+1;an();}//1>3 m=min(d[t][2],c-d[t][3]); if(pd(d[t][1],d[t][2]-m,d[t][3]+m,d[t][0])) {f[++w]=t;d[w][1]=d[t][1]; d[w][2]=d[t][2]-m;d[w][3]=d[t][3]+m;d[w][0]=d[t][0]+1;an();}//2>3 m=min(d[t][2],a-d[t][1]); if(pd(d[t][1]+m,d[t][2]-m,d[t][3],d[t][0])) {f[++w]=t;d[w][1]=d[t][1]+m; d[w][2]=d[t][2]-m;d[w][3]=d[t][3];d[w][0]=d[t][0]+1;an();}//2>1 m=min(d[t][3],a-d[t][1]); if(pd(d[t][1]+m,d[t][2],d[t][3]-m,d[t][0])) {f[++w]=t;d[w][1]=d[t][1]+m; d[w][2]=d[t][2];d[w][3]=d[t][3]-m;d[w][0]=d[t][0]+1;an();}//3>1 m=min(d[t][3],b-d[t][2]); if(pd(d[t][1],d[t][2]+m,d[t][3]-m,d[t][0])) {f[++w]=t;d[w][1]=d[t][1]; d[w][2]=d[t][2]+m;d[w][3]=d[t][3]-m;d[w][0]=d[t][0]+1;an();}//3>2 t++; } } int main() { cin>>a>>b>>c>>e; search(); if(ans==0)cout<<"no answer"; return 0; } |
Subscribe
计数器 9527326
OI 课件=>
OI 课件=>