Problem Description
大家一定觉的运动以后喝可乐是一件很惬意的事情,但是seeyou却不这么认为。因为每次当seeyou买了可乐以后,阿牛就要求和seeyou一起分享这一瓶可乐,而且一定要喝的和seeyou一样多。但seeyou的手中只有两个杯子,它们的容量分别是N 毫升和M 毫升 可乐的体积为S (S<101)毫升 (正好装满一瓶) ,它们三个之间可以相互倒可乐 (都是没有刻度的,且 S==N+M,101>S>0,N>0,M>0) 。聪明的ACMER你们说他们能平分吗?如果能请输出倒可乐的最少的次数,如果不能输出"NO"。
Input
三个整数 : S 可乐的体积 , N 和 M是两个杯子的容量,以"0 0 0"结束。
Output
如果能平分的话请输出最少要倒的次数,否则输出"NO"。
Sample Input
Sample Output
NO
3
#include<iostream>
#include<queue>
#include<cstring>
using namespace std;
struct node
{
int bucket[3];
int step;
};
bool matrix[101][101][101];
int bfs(int a,int b,int c)
{
int half,st[3],i,j;;
node cur,temp;
memset(matrix,0,sizeof(matrix));
queue<node>que;
st[0]=a,st[1]=b,st[2]=c;
half=a>>1;
cur.bucket[0]=st[0],cur.bucket[1]=0,cur.bucket[2]=0,cur.step=0;
matrix[a][0][0]=1;
que.push(cur);
while(!que.empty())
{
cur=que.front(),que.pop();
if((cur.bucket[0]==half&&cur.bucket[1]==half)||(cur.bucket[1]==half&&cur.bucket[2]==half)||(cur.bucket[2]==half&&cur.bucket[0]==half))
{
return cur.step;
}
cur.step++;
for(i=0; i<3; i++)
{
if(cur.bucket[i]>0)
for(j=0; j<3; j++)
{
temp=cur;
if(i==j)continue;
if(temp.bucket[i]<=st[j]-temp.bucket[j])
{
temp.bucket[j]+=temp.bucket[i];
temp.bucket[i]=0;
}
else
{
temp.bucket[i]-=st[j]-temp.bucket[j];
temp.bucket[j]=st[j];
}
if(!matrix[temp.bucket[0]][temp.bucket[1]][temp.bucket[2]])
{
matrix[temp.bucket[0]][temp.bucket[1]][temp.bucket[2]]=1;
que.push(temp);
}
}
}
}
return 0;
}
int main()
{
int a,b,c,ans;
while(cin>>a>>b>>c,a||b||c)
{
if(a%2)
{
cout<<"NO"<<endl;
continue;
}
ans=bfs(a,b,c);
if(ans==0)cout<<"NO"<<endl;
else cout<<ans<<endl;
}
return 0;
}
分享到:
相关推荐
算法-非常可乐(HDU-1495)(包含源程序).rar
HDU的1250,主要是利用高精度加法,但是代码有点繁琐,效率不是很高
杭电ACMhdu1163
HDU1059的代码
hdu1001解题报告
hdu 1574 passed sorce
HDU的一题........HDU DP动态规
hdu acm 教案 搜索入门 hdu acm 教案 搜索入门
hdu2101AC代码
搜索 dfs 解题代码 hdu1241
hdu 5007 Post Robot 字符串枚举。 暴力一下就可以了。
hdu acm 教案 动态规划(1) hdu acm 教案 动态规划(1)
ACM HDU题目分类,我自己总结的大概只有十来个吧
hdu 1166线段树代码
HDU最全ac代码
hdu动态规划算法集锦
自己做的HDU ACM已经AC的题目
hdu题目分类
HDU图论题目分类