题目大意：有一瓶可乐，已知容积，但是不知道刻度，现在有两个杯子，可以从一个杯子倒到另一个杯子
问最少几次可以把可乐评分 两个杯子容积之和为可乐容积
思路：有大佬推出了公式可以直接推出 次数a/gcd（b，c）-1 如果这个数是偶数则可以输出，不然输出no
另一个就是bfs的，bfs时走法很多，比较繁琐，都是复制粘贴。菜鸡写的很长 还差点超时
#include<stdio.h>#include<string.h>int book[105][105][105];int x,y,z;struct node{int a;int b;int c;int step;}queue[1000005];int bfs(int i,int j,int k);int main(void){while(scanf("%d%d%d",&x,&y,&z),x&&y&&z){if(y<z){int t;t=y;y=z;z=t;}memset(book,0,sizeof(book));int ans;if(x%2==0)//判断是不是偶数，不是的话直接输出NOans=bfs(x,0,0);elseans=0;if(ans)printf("%d\n",ans);elseprintf("NO\n");}return 0;} int bfs(int i,int j,int k){book[i][j][k]=1;int head=0;int tail=1;queue[head].a=i;queue[head].b=j;queue[head].c=k;queue[head].step=0;while(head<tail){if(queue[head].a==x/2&&queue[head].b==x/2)//判断是不是已经平分return queue[head].step;if(queue[head].a!=0){ if(queue[head].a>y-queue[head].b) //下面就是pour，看起来很繁琐，其实都是复制粘贴过去的{ if(!book[queue[head].a-y+queue[head].b][y][queue[head].c]){queue[tail].a=queue[head].a-y+queue[head].b;queue[tail].b=y;queue[tail].c=queue[head].c; queue[tail].step=queue[head].step+1;book[queue[head].a-y+queue[head].b][y][queue[head].c]=1;if(queue[tail].a==x/2&&queue[tail].b==x/2)return queue[tail].step;tail++;}}else{ if(!book[0][queue[head].a+queue[head].b][queue[head].c]){queue[tail].a=0;queue[tail].b=queue[head].a+queue[head].b;queue[tail].c=queue[head].c;queue[tail].step=queue[head].step+1;if(queue[tail].a==x/2&&queue[tail].b==x/2)return queue[tail].step;tail++;book[0][queue[head].a+queue[head].b][queue[head].c]=1; }}if(queue[head].a>z-queue[head].c) { if(!book[queue[head].a-z+queue[head].c][queue[head].b][z]){queue[tail].a=queue[head].a-z+queue[head].c;queue[tail].c=z;queue[tail].b=queue[head].b;queue[tail].step=queue[head].step+1;book[queue[head].a-z+queue[head].c][queue[head].b][z]=1;if(queue[tail].a==x/2&&queue[tail].b==x/2)return queue[tail].step;tail++;}} else { if(!book[0][queue[head].b][queue[head].a+queue[head].c]){queue[tail].a=0;queue[tail].b=queue[head].b;queue[tail].c=queue[head].a+queue[head].c;queue[tail].step=queue[head].step+1;if(queue[tail].a==x/2&&queue[tail].b==x/2)return queue[tail].step;tail++;book[0][queue[head].b][queue[head].a+queue[head].c]=1;}}}if(queue[head].b!=0){ if(!book[queue[head].a+queue[head].b][0][queue[head].c]){queue[tail].a=queue[head].a+queue[head].b;queue[tail].b=0;queue[tail].c=queue[head].c; queue[tail].step=queue[head].step+1;if(queue[tail].a==x/2&&queue[tail].b==x/2)return queue[tail].step;tail++;book[queue[head].a+queue[head].b][0][queue[head].c]=1;}if(queue[head].b>(z-queue[head].c)) { if(!book[queue[head].a][queue[head].b-z+queue[head].c][z]){queue[tail].a=queue[head].a;queue[tail].c=z;queue[tail].b=queue[head].b-z+queue[head].c; queue[tail].step=queue[head].step+1;book[queue[head].a][queue[head].b-z+queue[head].c][z]=1;if(queue[tail].a==x/2&&queue[tail].b==x/2)return queue[tail].step;tail++;}} else { if(!book[queue[head].a][0][queue[head].b+queue[head].c]){queue[tail].a=queue[head].a;queue[tail].b=0;queue[tail].c=queue[head].b+queue[head].c;queue[tail].step=queue[head].step+1;if(queue[tail].a==x/2&&queue[tail].b==x/2)return queue[tail].step;tail++;book[queue[head].a][0][queue[head].b+queue[head].c]=1;}} }if(queue[head].c!=0){ if(!book[queue[head].a+queue[head].c][queue[head].b][0]){queue[tail].a=queue[head].a+queue[head].c;queue[tail].b=queue[head].b;queue[tail].c=0; queue[tail].step=queue[head].step+1;book[queue[head].a+queue[head].c][queue[head].b][0]=1;if(queue[tail].a==x/2&&queue[tail].b==x/2)return queue[tail].step;tail++;}if(queue[head].c>(y-queue[head].b)) { if(!book[queue[head].a][y][queue[head].c-y+queue[head].b]){queue[tail].a=queue[head].a;queue[tail].c=queue[head].c-y+queue[head].b;queue[tail].b=y; queue[tail].step=queue[head].step+1;book[queue[head].a][y][queue[head].c-y+queue[head].b]=1; if(queue[tail].a==x/2&&queue[tail].b==x/2)return queue[tail].step;tail++;} }else { if(!book[queue[head].a][queue[head].b+queue[head].c][0]){queue[tail].a=queue[head].a;queue[tail].b=queue[head].b+queue[head].c;queue[tail].c=0;queue[tail].step=queue[head].step+1; if(queue[tail].a==x/2&&queue[tail].b==x/2)return queue[tail].step;tail++;book[queue[head].a][queue[head].b+queue[head].c][0]=1;} }}head++;}return 0; }
