非常可乐---hdu 1495（BFS）
2024-08-26 03:26:19
http://acm.hdu.edu.cn/showproblem.php?pid=1495
题意：
有3个杯子a b c；a=b+c；然后刚开始时只有a是满的，其它为空的，然后a b c三个之间互相倒，假如说a倒入b中，只有当b满或a空时，才算倒一次；
a=4,b=1;c=3;
因为刚开始只有a中有；
先让a倒入c中3；step++;
c倒入b中1；step++;
b倒入a中1；step++;此时a和c中各有2；
代码如下：
#include<iostream>
#include<stdio.h>
#include<string.h>
#include<queue>
#include<cmath>
#define N 120
using namespace std; struct node
{
int a,b,c,step;
friend bool operator<(node a,node b)
{
return a.step>b.step;
}
};
int vis[N][N][N];
int BFS(int a,int b,int c)
{
node q,p;
priority_queue<node>Q;
memset(vis,,sizeof(vis));
p.a=a;p.b=;p.c=;p.step=;
vis[p.a][p.b][p.c]=;
Q.push(p);
while(!Q.empty())
{
q=Q.top();
Q.pop();
if((q.a==a/&&q.b==a/)||(q.b==a/&&q.c==a/)||(q.a==a/&&q.c==a/) )
return q.step;
if(q.a!=)//a->其他；
{
if(q.a<=b-q.b)//a->b;如果a中的全都能倒到b中；
{
p.a=;
p.b=a-q.c;
p.c=q.c;
p.step=q.step+;
}
else//a不能全到完；因为b满了；
{
p.a=a-b-q.c;
p.b=b;
p.c=q.c;
p.step=q.step+;
}
if(vis[p.a][p.b][p.c]==)
{
vis[p.a][p.b][p.c]=;
Q.push(p);
} //以下同理；
if(q.a<=b-q.c)//a->c;如果a中的全都能倒到c中；
{
p.a=;
p.b=q.b;
p.c=a-q.b;
p.step=q.step+;
}
else//a不能全到完；因为c满了；
{
p.a=a-c-q.b;
p.b=q.b;
p.c=c;
p.step=q.step+;
}
if(vis[p.a][p.b][p.c]==)
{
vis[p.a][p.b][p.c]=;
Q.push(p);
}
} if(q.b!=)//b->其他；
{
if(q.b<=a-q.a)//b->a;如果b中的全都能倒到a中；
{
p.a=a-q.c;
p.b=;
p.c=q.c;
p.step=q.step+;
} if(vis[p.a][p.b][p.c]==)
{
vis[p.a][p.b][p.c]=;
Q.push(p);
} //以下同理；
if(q.b<=c-q.c)//b->c;如果b中的全都能倒到c中；
{
p.a=q.a;
p.b=;
p.c=a-q.a;
p.step=q.step+;
}
else//b不能全到完；因为c满了；
{
p.a=q.a;
p.b=a-q.a-c;
p.c=c;
p.step=q.step+;
}
if(vis[p.a][p.b][p.c]==)
{
vis[p.a][p.b][p.c]=;
Q.push(p);
}
} if(q.c!=)//c->其他；
{
if(q.c<=a-q.a)//c->a;如果c中的全都能倒到a中；
{
p.a=a-q.b;
p.b=q.b;
p.c=;
p.step=q.step+;
} if(vis[p.a][p.b][p.c]==)
{
vis[p.a][p.b][p.c]=;
Q.push(p);
} //以下同理；
if(q.c<=b-q.b)//c->b;如果c中的全都能倒到b中；
{
p.a=q.a;
p.b=a-q.a;
p.c=;
p.step=q.step+;
}
else//c不能全到完；因为b满了；
{
p.a=q.a;
p.b=b;
p.c=a-q.a-b;
p.step=q.step+;
}
if(vis[p.a][p.b][p.c]==)
{
vis[p.a][p.b][p.c]=;
Q.push(p);
}
}
}
return -;
} int main()
{
int a,b,c,ans;
while(scanf("%d%d%d",&a,&b,&c),a+b+c)
{
if(a%==)
{
printf("NO\n");
continue;
}
else
{
ans=BFS(a,b,c);
if(ans==-)
printf("NO\n");
else
printf("%d\n",ans);
}
}
return ;
}
最新文章
- html与css面试结合工作的总结难点
- iOS开发 滤镜的使用
- CentOS 7 ssh脚本 求两个数值的“和”，“乘积”，”商“
- JQGrid 学习1
- react在jsx语法中实现for循环
- [翻译]AKKA笔记 - LOGGING与测试ACTORS -2 (二)
- 20145304 Java第六周学习报告
- AngularJS Best Practices: ngRoute
- Xml序列化、反序列化帮助类
- Wikioi 1020 孪生蜘蛛 Label:Floyd最短路
- Django中如何配置Database缓存？
- 微信支付开发若干问题总结，API搞死人(谢谢ζั͡ޓއއއ๓http://www.thinkphp.cn/code/1620.html)血淋淋的教训，第二次栽这里了
- UrlDownloadFile, 线程下载文件, 带进度条
- 银行家算法java实现
- 【JavaScript学习】-JS内置对象1-对象概述
- 通过java程序调用ant build.xml配置文件中指定的target
- Protocol Buffers简明教程
- 1.7Oob同类中不同方法间的互相调用
- Spring源码阅读（四）
- RunAsAdmin