三个水杯
时间:2023-12-13 10:07:02
描述
给三个杯子,大小不一,只有最大的杯子里装满了水,剩下的两个是空杯子。三个杯子相互倒水,杯子没有标记,只能根据给定的杯子的体积来计算。现在你需要写一个程序来输出最初的状态。
输入
一行整数N(050)表示N组测试数据 接下来,每组测试数据有两行,第一行给出三个整数V1 V2 V3 (V1>V2>V3 V1<100 V3>0)表示三杯的体积。 第二行给出三个整数E1 E2 E3 (体积小于或等于相应的水杯体积)表示我们需要的最终状态
输出
每行输出相应测试数据的倒水次数最少。如果输出达不到目标状态-1
样例输入
2 6 3 1 4 1 1 9 3 2 7 1 1
样例输出
3-1
http:
//acm.nyist.net/JudgeOnline/problem.php?pid=21
六种状态0->1,1->0,1->2,2->1,2->3,3->2
#include
#include #include #include using namespace std; int e1,e2,e3; struct node { int step; int v[3]; }; int cap[4]; bool vis[105][105][105]; void pour(int dest,int sour,node& t) { int water=cap[dest]-t.v[dest]; if(t.v[sour]<=water) { t.v[dest]+=t.v[sour]; t.v[sour]=0; } else { t.v[dest]+=water; t.v[sour]-=water; } } int bfs() { node s; s.v[0]=cap[0];s.v[1]=0;s.v[2]=0; s.step=0; vis[cap[0]][0][0]=true; queue q; q.push(s); while(!q.empty()) { node tmp=q.front(); q.pop(); if(tmp.v[0]==e1&&tmp.v[1]==e2&&tmp.v[2]==e3)return tmp.step; for(int i=0;i<3;i++) { for(int j=1;j<3;j++) { int k=(i+j)%3;//模拟三种状态 if(tmp.v[i]==0||tmp.v[k]>=cap[k])continue; node x=tmp; pour(k,i,x); // cout<