本文主要是介绍HDU 1495 非常可乐 (BFS)，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
非常可乐
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 7729 Accepted Submission(s): 3089
Problem Description
大家一定觉的运动以后喝可乐是一件很惬意的事情，但是seeyou却不这么认为。因为每次当seeyou买了可乐以后，阿牛就要求和seeyou一起分享这一瓶可乐，而且一定要喝的和seeyou一样多。但seeyou的手中只有两个杯子，它们的容量分别是N 毫升和M 毫升 可乐的体积为S （S<101）毫升 (正好装满一瓶) ，它们三个之间可以相互倒可乐 (都是没有刻度的，且 S==N+M，101＞S＞0，N＞0，M＞0) 。聪明的ACMER你们说他们能平分吗？如果能请输出倒可乐的最少的次数，如果不能输出"NO"。
Input
三个整数 : S 可乐的体积 , N 和 M是两个杯子的容量，以"0 0 0"结束。
Output
如果能平分的话请输出最少要倒的次数，否则输出"NO"。
Sample Input
7 4 3 4 1 3 0 0 0
Sample Output
NO 3
Author
seeyou
Source
“2006校园文化活动月”之“校庆杯”大学生程序设计竞赛暨杭州电子科技大学第四届大学生程序设计竞赛
题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=1495
题目大意：3个无刻度杯子倒水要求均分，求最少倒几次
题目分析：6种情况bfs，hash一下状态
题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=1495
题目大意：3个无刻度杯子倒水要求均分，求最少倒几次
题目分析：6种情况bfs，hash一下状态
#include <cstdio>
#include <cstring>
#include <queue>
using namespace std;
int const MAX = 1e6 + 5;
int s, n, m;
bool vis[MAX];struct NODE
{int p1, p2, p3;int step;
}nd[MAX];void make_vis(NODE p)
{vis[p.p1 + 100 * p.p2 + 10000 * p.p3] = true;
}bool judge_vis(NODE p)
{return vis[p.p1 + 100 * p.p2 + 10000 * p.p3];
}int BFS()
{queue <NODE> q;NODE st;st.p1 = s;st.p2 = 0;st.p3 = 0;st.step = 0;q.push(st);make_vis(st);while(!q.empty()){NODE t = q.front(), cur;q.pop();//printf("t.p1 = %d t.p2 = %d t.p3 = %d t.step = %d\n", t.p1, t.p2, t.p3, t.step);if(t.p1 == t.p2 && t.p1 == s / 2)return t.step;if(t.p2 == t.p3 && t.p2 == s / 2)return t.step;if(t.p1 == t.p3 && t.p1 == s / 2)return t.step;int r = n - t.p2;if(r > t.p1)r = t.p1;cur.p2 = t.p2 + r;cur.p1 = t.p1 - r;cur.p3 = t.p3;if(!judge_vis(cur)){cur.step = t.step + 1;q.push(cur);make_vis(cur);}r = m - t.p3;if(r > t.p1)r = t.p1;cur.p3 = t.p3 + r;cur.p1 = t.p1 - r;cur.p2 = t.p2;if(!judge_vis(cur)){cur.step = t.step + 1;q.push(cur);make_vis(cur);}r = m - t.p3;if(r > t.p2)r = t.p2;cur.p3 = t.p3 + r;cur.p2 = t.p2 - r;cur.p1 = t.p1;if(!judge_vis(cur)){cur.step = t.step + 1;q.push(cur);make_vis(cur);}r = s - t.p1;if(r > t.p2)r = t.p2;cur.p1 = t.p1 + r;cur.p2 = t.p2 - r;cur.p3 = t.p3;if(!judge_vis(cur)){cur.step = t.step + 1;q.push(cur);make_vis(cur);}r = s - t.p1;if(r > t.p3)r = t.p3;cur.p1 = t.p1 + r;cur.p3 = t.p3 - r;cur.p2 = t.p2;if(!judge_vis(cur)){cur.step = t.step + 1;q.push(cur);make_vis(cur);}r = n - t.p2;if(r > t.p3)r = t.p3;cur.p2 = t.p2 + r;cur.p3 = t.p3 - r;cur.p1 = t.p1;if(!judge_vis(cur)){cur.step = t.step + 1;q.push(cur);make_vis(cur);}}return -1;
}int main()
{while(scanf("%d %d %d", &s, &n, &m) != EOF && (n + m + s)){memset(vis, false, sizeof(vis));if(s & 1){printf("NO\n");continue;}int ans = BFS();if(ans == -1)printf("NO\n");elseprintf("%d\n", ans);}
}
这篇关于HDU 1495 非常可乐 (BFS)的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
