- 浏览: 196986 次
- 性别:
- 来自: 武汉
文章分类
- 全部博客 (137)
- c++ (74)
- c++,算法,回溯 (2)
- DP问题。 (9)
- DP问题,0/1背包问题 (3)
- 数学问题 (6)
- 贪心算法 (10)
- 排序 (16)
- 数据结构 (7)
- 容器 (2)
- 模拟问题 (2)
- 水题 (8)
- 并查集 (3)
- 非技术 (2)
- 素数问题 (1)
- DFS (3)
- 二叉树 (1)
- 递归 (1)
- 图论 (5)
- 最小生成树 (5)
- 最短路径 (6)
- bell_flaod算法 (2)
- hash (3)
- 二分查找 (1)
- 搜索 (5)
- BFS (5)
- STL (3)
- 字符串hash (1)
- 拓扑排序 (1)
- 字典树 (4)
- 哈弗曼树 (1)
- KMP (7)
- 线段树 (9)
- 树状数组 (6)
- 全排列 (2)
- DP问题 (2)
- LCS (1)
- 最长不下降子序列 (2)
- 面试经验 (3)
题意:给出两个容积分别为 a 和 b 的pot,按照以下三种操作方式,求出能否在一定步数后,使者两个pot的其中一个的水量为c。
1.FILL(i):将ipot倒满水。
2.DROP(i):将ipot倒空水。
3.POUR(i,j): 将ipot的水倒到jpot上,直至要么ipot为空,要么jpot为满。
思路:bfs求最短路径,与1426类似,只是每个节点的子节点数为6个而已。
代码如下:
#include<iostream> using namespace std; const int Max = 101; struct node { int ope; int a; int b; node *pre; }que[Max * Max]; // 队列结点,ope记录第几种操作,a,b记录此结点两个pot的水的数量。 bool vis[Max][Max]; char str[6][10] = {"FILL(1)", "FILL(2)", "DROP(1)", "DROP(2)", "POUR(1,2)", "POUR(2,1)"}; // 各操作对应输出的字符串。 int min(int a, int b) { return a < b ? a : b; } void print(node now) { if(now.pre != NULL) { print(*now.pre); cout << str[now.ope] << endl; } }//递归输出答案个人认为写得很巧妙 void bfs(int a, int b, int c) { int steps = 0; int head = 0, tail = 1; que[0].a = que[0].b = 0; que[0].pre = NULL; while(tail - head > 0) { int count = tail - head; while(count --)//每一种情况都要考虑六种情况 { node now = que[head]; if(now.a == c || now.b == c) { cout << steps << endl; print(now); return; } if(!vis[a][now.b]) { que[tail].ope = 0; que[tail].a = a; que[tail].b = now.b; que[tail].pre = &que[head]; vis[a][now.b] = true; tail ++; } if(!vis[now.a][b]) { que[tail].ope = 1; que[tail].a = now.a; que[tail].b = b; que[tail].pre = &que[head]; vis[now.a][b] = true; tail ++; } if(!vis[0][now.b]) { que[tail].ope = 2; que[tail].a = 0; que[tail].b = now.b; que[tail].pre = &que[head]; vis[0][now.b] = true; tail ++; } if(!vis[now.a][0]) { que[tail].ope = 3; que[tail].a = now.a; que[tail].b = 0; que[tail].pre = &que[head]; vis[now.a][0] = true; tail ++; } int wat1 = min(now.a, b - now.b); if(!vis[now.a - wat1][now.b + wat1]) { que[tail].ope = 4; que[tail].a = now.a - wat1; que[tail].b = now.b + wat1; que[tail].pre = &que[head]; vis[now.a - wat1][now.b + wat1] = true; tail ++; } int wat2 = min(a - now.a, now.b); if(!vis[now.a + wat2][now.b - wat2]) { que[tail].ope = 5; que[tail].a = now.a + wat2; que[tail].b = now.b - wat2; que[tail].pre = &que[head]; vis[now.a + wat2][now.b - wat2] = true; tail ++; } head ++; } steps ++; } cout << "impossible" << endl; } int main() { int a, b, c; cin >> a >> b >> c; memset(vis, false, sizeof(vis));//初始化 vis[0][0] = true;//初始化 bfs(a, b, c); return 0; }
发表评论
-
虚函数、纯虚函数、虚基类、抽象类、虚函数继承、虚继承
2013-08-29 14:34 789虚函数:虚函数是C++中用于实现多态(polymorphis ... -
排序算法总结
2013-05-17 11:00 788选择排序、快速排序、希尔排序、堆排序不是稳定的排序算法, ... -
poj 3122
2012-12-11 19:51 814题意:作者要开一个生日party,他现在拥有n块高度都为1 ... -
poj 3273
2012-12-11 16:49 949题意:给你天数n,和每天需要花的钱,让你把这些天分成m份(每份 ... -
字典树学习材料
2012-05-30 14:29 937字典树,又称单词查找树,Trie树,是一种树形结构,典型应 ... -
poj 1159
2012-05-28 19:08 1400题目大意:给你一段字符串,让你求出在中间最少加入几个字符 ... -
poj 3176
2012-05-28 14:47 977大致题意: 输入一个n层的三角形,第i层有i个数,求从第 ... -
poj 1260
2012-05-28 09:54 1573题意解释: 有n个等级的珠宝,等级依次升高,等级越高价钱越高 ... -
poj 1836
2012-05-28 09:22 2673是POJ2533的扩展题。题意不难,令到原队列 ... -
poj 2533
2012-05-26 15:36 1208在做这道题目之前,首先让我们了解一下什么是LIS算法,LIS俗 ... -
poj 3267
2012-05-26 09:43 777从程序可以看出,第i个位置到L所删除的字符数,总是先取最坏情况 ... -
poj 1276
2012-05-25 16:20 2354题意: 这道题的意思是给你一堆钱,各种面值的都有,比 ... -
poj 1094
2012-05-25 13:54 1064题意:给出字母个数,和有限个有序对(a<b)求出能确定字 ... -
poj 3393
2012-05-23 17:00 1227大致题意: 科普文一篇,文章80%都是无用信息,因为 ... -
poj 3007
2012-05-14 10:21 950大致题意: 给定一个字符串,从任意位置把它切为两半, ... -
poj 3096
2012-05-10 21:09 965题意: 定义D-pairs表示取字符串s中相距为D的两个字母 ... -
poj 1426
2012-04-26 20:11 2118大致题意: 给出一个整数n,(1 <= n <= ... -
poj 1797
2012-04-24 15:05 1590题目大意是就是何处一个图,n个顶点和m条边,每个边都有最大承载 ... -
poj 1338
2012-04-23 10:20 1226题意:题目意思是求由2,3,5的乘积组成的数从大到小排列,从1 ... -
poj 2021
2012-04-19 15:00 896题意:Ted今年100岁,给出n对他家族的关系:“父 ...
相关推荐
北大POJ1426-Find The Multiple【BFS+同余模】 解题报告+AC代码
SPOJ3 AC程序 BF SPOJ3 AC程序 BF SPOJ3 AC程序 BF
北大POJ3026-Borg Maze【BFS+Prim】 解题报告+AC代码
BFS POJ 3278 POJ 1426 POJ 3126 POJ 3414 POJ 2251 简单搜索技巧和剪枝 POJ 1010 :star: POJ 2362 POJ 1011(搜索+剪枝) POJ 1416 POJ 2676 POJ 1129:white_question_mark: 数据结构 串 POJ 1016 POJ 1035 POJ ...
POJ 3131 双向BFS解立体八数码问题
POJ各题算法分类和题目推荐 ACM必看 POJ各题算法分类和题目推荐 ACM必看 POJ各题算法分类和题目推荐 ACM必看
北大POJ3278-Catch That Cow 解题报告+AC代码
业余爱好。所以,算法不一定好,CODING也不一定佳,效率不一定高,只是能通过online judge而已。
因为考虑到通过砖墙时和空地所花的时间不同,所以不能使用一般的BFS广搜来做。用DFS深搜,你会发现时间复杂非常高,必然会超时(最大是300*300的图)。本题可以使用改进过的广搜或优先队列+bfs 或 记忆化广搜三种...
本人自己总结的acm广度搜索实例代码,经典的几个代码程序 只有代码,没有题目,主要是在POJ的。我是在ubuntu下压缩的。
poj 的代码。 所有 C++ 代码。 bfs.cpp:我的 poj 3984 解决方案。最短路径的 BFS,并递归地追溯路径。 解决这个问题我想起了很多:如何定义mutli-dim vector,如何定义队列,如何定义struct数组,如何定义方向,...
POJ 1190 --- dfs + pruning(Strong) 4. UVALive 2243 --- dfs 5. FZU 2196 --- double bfs 6. PKU 1426 --- bfs + pruning 7. BNU 1038 --- dfs transform 8. PKU 1562 --- dfs transform 9. HDU 1253 --- basic ...
算法入门—广度优先搜索—raphealguo
leetcode中国 MyAlgorithmSolutions 记录我所有的算法/数据结构 目录 ...笔记 数据结构 算法(第四版) ...POJ 大二 2019 新生赛 蓝桥杯模拟 蓝桥杯学习 bfs 大数 dfs/抽象dfs 逻辑 测试 栈/递归 清华oj入门
动态计划、贪婪、枚举、BFS、DFS 数学 类似于数论 给读者 大多数 cpp 文件是使用 Visual Studio IDE 创建的,其他文件是使用 Codeblocks IDE 创建的。 代码问题包含 在由考试(尤其是 PKU)命名的目录中 你可以在...
第一阶段:练经典常用算法,...6.BFS、DFS,同时熟练hash表(要熟,要灵活,代码要简) 7.数学上的有:辗转相除(两行内),线段交点、多角形面积公式. 8. 调用系统的qsort, 技巧很多,慢慢掌握. 9. 任意进制间的转换
poj: 顶级编码器: 代码力量: 间谍: 佐伊: 福伊: 紫外线: ltOJ: leetcode: 重复部分: 稀疏动态规划 分而治之的问题 图算法问题 试题 搜索问题、DFS、BFS 和切边 排序:堆排序 流算法。 : 布隆过滤器: 卢: ...
2.6 随机素数测试和大数分解 (POJ 1811) . . . . . . . . . . . . . . . . . . . . . . . 29 2.7 欧拉函数 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 32 2.7.1 分解质因素求...