hdu1495（bfs）
2024-08-25 11:16:13
题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=1495
题意：有三个杯子，开始时第一个杯子装满水（体积为a），倒来倒去，得到其中2个杯里的水的体积都为a/2，求最小次数，不存在就输出NO。
分析：因为被子没有刻度，所以倒入时要倒满或倒完才能保证知道容积，即有6种情况来分别遍历。
#include <iostream>
#include <cstdlib>
#include <queue>
#include <vector>
#include <cstdio>
#include <map>
#include <cstring>
#include <algorithm>
#define INF 100000000
#define maxn 111111
#define ll __int64
#define lson 1,m,rt<<1
#define rson m+1,r,rt<<1|1
using namespace std;
int vis[][][];
int a,b,c,flag;
struct node
{
int x,y,z;
int step;
};
int judge(node k)
{
if((k.x==k.y&&k.z==)||(k.x==k.z&&k.y==)||(k.y==k.z&&k.x==))
return ;
return ;
}
void bfs()
{
queue<node>que;
node now,next;
int num;
now.x=a;now.y=;
now.z=;now.step=;
vis[a][][]=;
que.push(now);
while(!que.empty())
{
now=que.front();que.pop();
if(judge(now))
{
printf("%d\n",now.step);
flag=;
return;
}
if(now.x>)//a倒入其他
{
if(b>now.y)//a倒入b
{
num=b-now.y;
next.z=now.z;
next.step=now.step+;
if(now.x>num)//a倒不完
{
next.x=now.x-num;
next.y=b;
}
else//倒完
{
next.y=now.x+now.y;
next.x=;
}
if(!vis[next.x][next.y][next.z])
{
vis[next.x][next.y][next.z]=;
que.push(next);
}
}
if(c>now.z)//a倒入c
{
num=c-now.z;
next.y=now.y;
next.step=now.step+;
if(now.x>num)//倒不完
{
next.x=now.x-num;
next.z=c;
}
else//倒完
{
next.z=now.x+now.z;
next.x=;
}
if(!vis[next.x][next.y][next.z])
{
vis[next.x][next.y][next.z]=;
que.push(next);
}
}
}
if(now.y>)//b倒入其他
{
if(a>now.x)
{
num=a-now.x;
next.z=now.z;
next.step=now.step+;
if(now.y>num)
{
next.y=now.y-num;
next.x=a;
}
else
{
next.x=now.x+now.y;
next.y=;
}
if(!vis[next.x][next.y][next.z])
{
vis[next.x][next.y][next.z]=;
que.push(next);
}
}
if(c>now.z)
{
num=c-now.z;
next.x=now.x;
next.step=now.step+;
if(now.y>num)
{
next.y=now.y-num;
next.z=c;
}
else
{
next.z=now.y+now.z;
next.y=;
}
if(!vis[next.x][next.y][next.z])
{
vis[next.x][next.y][next.z]=;
que.push(next);
}
}
}
if(now.z>)//c倒入其他
{
if(b>now.y)
{
num=b-now.y;
next.x=now.x;
next.step=now.step+;
if(now.z>num)
{
next.z=now.z-num;
next.y=b;
}
else
{
next.y=now.z+now.y;
next.z=;
}
if(!vis[next.x][next.y][next.z])
{
vis[next.x][next.y][next.z]=;
que.push(next);
}
}
if(a>now.x)
{
num=a-now.x;
next.y=now.y;
next.step=now.step+;
if(now.z>num)
{
next.z=now.z-num;
next.x=a;
}
else
{
next.x=now.x+now.z;
next.z=;
}
if(!vis[next.x][next.y][next.z])
{
vis[next.x][next.y][next.z]=;
que.push(next);
}
}
}
}
}
int main()
{
while(scanf("%d%d%d",&a,&b,&c)>)
{
if(a+b+c==)break;
if(a%)//剪枝
{
puts("NO");
continue;
}
memset(vis,,sizeof(vis));
flag=;
bfs();
if(!flag)puts("NO");
}
}
最新文章
- vs插件ZunKoIDE
- mysql 安装失败解决方法
- 使用 HTML5 input 类型提升移动端输入体验
- [Spring MVC] - InitBinder验证
- NHibernate系列文章六：NHibernate数据类型映射
- MyBatis crud操作
- JavaScript基础15——js的DOM对象
- Objective-C 高性能的循环遍历 forin - NSEnumerator - 枚举 优化
- （转）STL
- log4cpp的初步使用
- 最佳新秀SSH十六Struts2它是如何工作的内部
- 通过数据，修改金蝶ERP的收料通知单不合格和合格数量，修改生产投料单，委外发出数量
- Log4J：Log4J三大组件：Logger+Appender+Layout 格式化编程详解
- 手把手教你用Vue造轮子（3）：开发可排序的表格组件
- BZOJ5207 : [Jsoi2017]隧道
- 【读书笔记】iOS-使用蓝牙
- Python3学习之路~2.10 修改haproxy配置文件
- JAVA个人小程序GUI篇-收银（标签、按钮、复选框、下拉标、文本域、表格······）
- 计算机网络知识—(TCP)
- swift MD5 加密方法