非常可乐

大家一定觉的运动以后喝可乐是一件很惬意的事情，但是seeyou却不这么认为。因为每次当seeyou买了可乐以后，阿牛就要求和seeyou一起分享这一瓶可乐，而且一定要喝的和seeyou一样多。但seeyou的手中只有两个杯子，它们的容量分别是N 毫升和M 毫升 可乐的体积为S （S<101）毫升　(正好装满一瓶) ，它们三个之间可以相互倒可乐 (都是没有刻度的，且 S==N+M，101＞S＞0，N＞0，M＞0) 。聪明的ACMER你们说他们能平分吗？如果能请输出倒可乐的最少的次数，如果不能输出"NO"。

三个整数 : S 可乐的体积 , N 和 M是两个杯子的容量，以"0 0 0"结束。

如果能平分的话请输出最少要倒的次数，否则输出"NO"。

7 4 34 1 30 0 0

NO3

seeyou

 

转载地址:

 

思路：搜索题，第一次做这种类型的题目吧，一开始表示不怎么明白题意所说的东东。其实就是要你判断可乐能不能被平分........

有六种状态，从a瓶到b瓶，a-->c

b-->a     b-->c

c-->a     c-->b

然后每种状态里面又分两种不同情况，可以将此瓶的水全部清空，不能清空......

然后广搜就可以了........

#include
    

#include
    
      #include
     
       #include
      
        using namespace std; int vist[105][105][105],a,b,c; struct node {     int a,b,c;     int step; }s[105]; int sum=0; void bfs() {     queue
       
        q;     memset(vist,0,sizeof(vist));     node p1;     p1.a=a;     p1.b=0;     p1.c=0;     p1.step=0;     q.push(p1);     vist[p1.a][0][0]=1;     while(!q.empty())     {         p1=q.front();         q.pop();         if((p1.a==a/2&&p1.b==a/2)||(p1.a==a/2&&p1.c==a/2)||(p1.b==a/2&&p1.c==a/2))         {             printf("%d\n",p1.step);             return;         }         node p2;             if(p1.a!=0)         {             if(p1.a>b-p1.b)             {                 p2.a=p1.a-(b-p1.b);                 p2.b=b;                 p2.c=p1.c;                 p2.step=p1.step+1;             }             else            {                 p2.a=0;                 p2.b=p1.b+p1.a;                 p2.c=p1.c;                 p2.step=p1.step+1;             }             if(!vist[p2.a][p2.b][p2.c])             {                 vist[p2.a][p2.b][p2.c]=1;                 q.push(p2);             }         }                   if(p1.a!=0)         {             if(p1.a>c-p1.c)             {                 p2.a=p1.a-(c-p1.c);                 p2.b=p1.b;                 p2.c=c;                 p2.step=p1.step+1;             }             else            {                 p2.a=0;                 p2.b=p1.b;                 p2.c=p1.c+p1.a;                 p2.step=p1.step+1;             }             if(!vist[p2.a][p2.b][p2.c])             {                 vist[p2.a][p2.b][p2.c]=1;                 q.push(p2);             }         }                   if(p1.b!=0)         {             if(p1.b>a-p1.a)             {                 p2.b=p1.b-(a-p1.a);                 p2.a=a;                 p2.c=p1.c;                 p2.step=p1.step+1;             }             else            {                 p2.b=0;                 p2.a=p1.a+p1.b;                 p2.c=p1.c;                 p2.step=p1.step+1;             }             if(!vist[p2.a][p2.b][p2.c])             {                 vist[p2.a][p2.b][p2.c]=1;                 q.push(p2);             }         }                   if(p1.b!=0)         {             if(p1.b>c-p1.c)             {                 p2.b=p1.b-(c-p1.c);                 p2.a=p1.a;                 p2.c=c;                 p2.step=p1.step+1;             }             else            {                 p2.b=0;                 p2.a=p1.a;                 p2.c=p1.c+p1.b;                 p2.step=p1.step+1;             }             if(!vist[p2.a][p2.b][p2.c])             {                 vist[p2.a][p2.b][p2.c]=1;                 q.push(p2);             }         }                   if(p1.c!=0)         {             if(p1.c>a-p1.a)             {                 p2.c=p1.c-(a-p1.a);                 p2.a=a;                 p2.b=p1.b;                 p2.step=p1.step+1;             }             else            {                 p2.c=0;                 p2.a=p1.a+p1.c;                 p2.b=p1.b;                 p2.step=p1.step+1;             }             if(!vist[p2.a][p2.b][p2.c])             {                 vist[p2.a][p2.b][p2.c]=1;                 q.push(p2);             }         }                   if(p1.c!=0)         {             if(p1.c>b-p1.b)             {                 p2.c=p1.c-(b-p1.b);                 p2.a=p1.a;                 p2.b=b;                 p2.step=p1.step+1;             }             else            {                 p2.c=0;                 p2.a=p1.a;                 p2.b=p1.b+p1.c;                 p2.step=p1.step+1;             }             if(!vist[p2.a][p2.b][p2.c])             {                 vist[p2.a][p2.b][p2.c]=1;                 q.push(p2);             }         }     }     printf("NO\n"); } int main() {     while(scanf("%d%d%d",&a,&b,&c)>0&&(a+b+c))     {         if(a%2==1)         {             printf("NO\n");             continue;         }         bfs();     }     return 0; }