题目大意：有一瓶可乐，已知容积，但是不知道刻度，现在有两个杯子，可以从一个杯子倒到另一个杯子
问最少几次可以把可乐评分 两个杯子容积之和为可乐容积
思路：有大佬推出了公式可以直接推出 次数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)//判断是不是偶数，不是的话直接输出NO ans=bfs(x,0,0); else ans=0; if(ans) printf("%d\n",ans); else printf("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; }
