ZCMU - 1978: 调酒壶里的酸奶
发布日期:2021-06-30 23:40:40
浏览次数:3
分类:技术文章
本文共 1272 字,大约阅读时间需要 4 分钟。
题目链接:
题目大意:略。
解题思路:记忆化搜索,对每个状态都有六种情况:
- 把A倒满
- 把B倒满
- 把A倒光
- 把B倒光
- 把A倒进B
- 把B倒进A
六个情况直接搜索就可以了...当然dfs是会超时的,需要用记忆化搜索。
AC 代码
#include#include #define mem(a,b) memset(a,b,sizeof a);#define INF 0x3f3f3f3fusing namespace std;typedef long long ll;typedef pair pii;queue q;int a,b,c;int vis[110][110], dis[110][110];void init(){ while(!q.empty()) q.pop(); mem(vis,0); mem(dis,0);}int bfs(){ dis[0][0]=0; vis[0][0]=1; q.push(make_pair(0,0)); int x,y,A,B; while(!q.empty()) { x=q.front().first, y=q.front().second; q.pop(); for(int i=1;i<=6;i++) { if(i==1) A=a, B=y; else if(i==2) A=x, B=b; else if(i==3) A=0, B=y; else if(i==4) A=x, B=0; else if(i==5) A=x+y>=b?x+y-b:0, B=x+y>=b?b:x+y; else if(i==6) B=x+y>=a?x+y-a:0, A=x+y>=a?a:x+y; if(!vis[A][B]) { vis[A][B]=1; dis[A][B]=1+dis[x][y]; if(A==c || B==c) return dis[A][B]; q.push(make_pair(A,B)); } } } return 0;}int main(){ while(~scanf("%d%d%d",&a,&b,&c)) { init(); int rs=bfs(); if(rs) printf("%d\n",rs); else puts("impossible"); } return 0;}
转载地址:https://lux-sun.blog.csdn.net/article/details/81082654 如侵犯您的版权,请留言回复原文章的地址,我们会给您删除此文章,给您带来不便请您谅解!
发表评论
最新留言
网站不错 人气很旺了 加油
[***.192.178.218]2024年04月23日 22时03分01秒
关于作者
喝酒易醉,品茶养心,人生如梦,品茶悟道,何以解忧?唯有杜康!
-- 愿君每日到此一游!
推荐文章
MySQL学习总结(一)
2019-05-01
MySQL学习总结(二)
2019-05-01
未来已至,5G加持下的云游戏将走向何方?
2019-05-01
备案问题汇总
2019-05-01
闭关三月!猛男逆道而行,四杀斩获阿里 / 腾讯 / 京东 / 百度等大厂 offer
2019-05-01
上线三天获 22w 浏览量!2021 最新一线大厂 Java 高级架构师面试题总结~
2019-05-01
电信物联网平台SOTA升级(软件升级)的全流程说明
2019-05-01
电信物联网平台插件开发相关总结
2019-05-01
CDH5.14 spark2.4.0配置python3 以及读取hive表
2019-05-01
【linux用户模块】用户/用户组的管理
2019-05-01
计算机网络 —— 数据链路层 3.
2019-05-01
计算机网络 —— 网络层 1.
2019-05-01
55. 跳跃游戏
2019-05-01
Dubbo+zookeeper 最简单的分布式搭建
2019-05-01
https数字证书交换过程
2019-05-01
http协议缓存详解
2019-05-01
Echarts使用及动态加载图表数据 折线图X轴数据动态加载
2019-05-01
高并发量网站解决方案
2019-05-01
接口api开发中安全性问题
2019-05-01