HDU 1495 非常可乐（BFS倒水问题）

题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=1495

题目大意：只有两个杯子，它们的容量分别是N 毫升和M 毫升可乐的体积为S （S<101）毫升　(正好装满一瓶) ，它们三个之间可以相互倒可乐 (都是没有刻度的，且 S==N+M，101＞S＞0，N＞0，M＞0) 。如果能将可乐平分则输出倒可乐的最少的次数，如果不能输出"NO"。

解题思路：题意很坑看了半天，就是要有两个杯子里的可乐都为S/2，S为奇数肯定不能平分的，接下来就模拟倒水（有六个选择）进行BFS，然后用数组记录各杯子里水的量作为状态。

 #include<cstdio>

 #include<cstring>

 #include<queue>

 using namespace std;

 const int N=;

 int A,B,C,ans;

 int vis[N][N][N];

 struct node{

     int a,b,c,step;

 }pre,now;

 bool bfs(){

     queue<node>q;

     now.a=A;

     now.b=;

     now.c=;

     now.step=;

     vis[A][][]=;

     q.push(now);

     while(!q.empty()){

         pre=q.front();

         q.pop();

         for(int i=;i<=;i++){

             int a,b,c;

             a=pre.a;

             b=pre.b;

             c=pre.c;

             if(i==){

                 if(a>B-b){

                     a-=(B-b);

                     b=B;

                 }

                 else{

                     b+=a;

                     a=;

                 }

             }

             if(i==){

                 a+=b;

                 b=;

             }

             if(i==){

                 if(b>C-c){

                     b-=(C-c);

                     c=C;

                 }

                 else{

                     c+=b;

                     b=;

                 }

             }

             if(i==){

                 if(c>B-b){

                     c-=(B-b);

                     b=B;

                 }

                 else{

                     b+=c;

                     c=;

                 }

             }

             if(i==){

                 if(a>C-c){

                     a-=(C-c);

                     c=C;

                 }

                 else{

                     c+=a;

                     a=;

                 }

             }

             if(i==){

                 a+=c;

                 c=;

             }

             if(vis[a][b][c])

                 continue;

             if(b==a&&b==A/||a==c&&a==A/){

                 ans=pre.step+;

                 return true;

             }

             vis[a][b][c]=;

             now.a=a;

             now.b=b;

             now.c=c;

             now.step=pre.step+;

             q.push(now);

         }

     }

     return false;

 }

 int main(){

     while(~scanf("%d%d%d",&A,&B,&C)){

         memset(vis,,sizeof(vis));

         ans=;

         if(A==&&B==&&C==)

             break;

         if(A&)

             puts("NO");

         else if(bfs())

             printf("%d\n",ans);

         else

             puts("NO");

     }

     return ;

 }

巴特西

HDU 1495 非常可乐（BFS倒水问题）

最新文章

热门文章