2025年倒水问题

倒水问题题意 有无限量的水 以及容量为 a 和 b 的两只杯子 要求通过两只杯子得到 c 单位的水 输入包含若干组数据 每组输入 a b c 要求输出得到 c 单位水需要进行的操作顺序 并且在成功得到 c 单位水后输出 success 一共有包含六种操作 1

大家好,我是讯享网,很高兴认识大家。

题意:

有无限量的水,以及容量为a和b的两只杯子,要求通过两只杯子得到c单位的水。
输入包含若干组数据,每组输入a,b,c,要求输出得到c单位水需要进行的操作顺序,并且在成功得到c单位水后输出success。
一共有包含六种操作:

1、倒满A杯(fill A)
2、倒满B杯(fill B)
3、倒空A杯(empty A)
4、倒空B杯(empty B)
5、把A的水倒到B杯并把A杯倒空或把B杯倒满(pour A B)
6、把B的水倒到A杯并把B杯倒空或把A杯倒满(pour B A)
输入样例:
2 7 5 2 7 4 

讯享网
输出样例
讯享网fill B pour B A success fill A pour A B fill A pour A B success 

思路:

1、构造一个结构体status,有a,b两个元素以及六种操作对应的函数。
2、声明map<status, bool> mp,用来判断是否到过status对应的情况,分别对应true和false;map<status, status> from,用来记录某status情况对应的前驱status,可以通过from[status]得到某status前驱状态。
3、使用bfs操作:首先将起始a=0,b=0的status插入队列中,每次取出队列中一个元素now,就对其进行六种操作,并且将操作结果插入队列中。循环直至队列清空或者now.a=c或者now.b=c,并将now作为bfs的返回值。
4、从bfs函数返回得到的status型数据,循环通过from[status]找到前驱状态,并且根据两者状态判断进行的操作并记录,直至前驱状态为status(0,0)。最后顺序输出所有操作即可。


讯享网

需要注意的是:

由于输入时可能包含多组数据,所以在完成一组数据的输出后,需要将队列、map等容器清空,否则会影响到下一组数据的操作。

代码:

#include <iostream> #include <queue> #include <map> using namespace std; string operation[] = { 
    "fill A","fill B","empty A","empty B","pour A B","pour B A" }; int aRemain, bRemain; int aMax, bMax; struct status { 
    int a, b; status() { 
   } status(int dx, int dy) { 
    a = dx; b = dy; } bool operator < (const status &s) const { 
    return a != s.a ? a < s.a : b < s.b; } bool operator == (const status &s) const { 
    return a == s.a&&b == s.b; } status filla() { 
    return status(aMax, b); } status fillb() { 
    return status(a, bMax); } status emptya() { 
    return status(0, b); } status emptyb() { 
    return status(a, 0); } status pourab() { 
    if (a > bMax - b) { 
    return status(a - bMax + b, bMax); } else { 
    return status(0, a + b); } } status pourba() { 
    if (b > aMax - a) { 
    return status(aMax, b - aMax + a); } else { 
    return status(0, b + a); } } }; queue<status> q; map<status, bool> mp;//用来判断是否到过status对应的情况 map<status, status> from;//用来记录status的前驱<后,前> void did(status x, status y) { 
    if (mp[x] == 0) { 
    mp[x] = 1; from[x] = y; q.push(x); } } status bfs(int a, int b, int c) { 
    status t(0, 0); q.push(t); mp[t] = 1; while (!q.empty()) { 
    status now = q.front(); q.pop(); if (now.a == c || now.b == c) { 
    return now; } did(now.filla(), now); did(now.fillb(), now); did(now.emptya(), now); did(now.emptyb(), now); did(now.pourab(), now); did(now.pourba(), now); } } int main() { 
    int c; while (cin >> aMax >> bMax >> c) { 
    status now = bfs(aMax, bMax, c); cout << now.a << " " << now.b << endl; vector<int> vec; int i = 0; while (now.a != 0 || now.b != 0) { 
    status pre = from[now]; //0.fill A if (pre.b == now.b&&now.a == aMax) { 
   //a不变b归零 vec.push_back(0); } //1.fill B if (pre.a == now.a&&now.b == bMax) { 
    vec.push_back(1); } //2.empty A if (pre.b == now.b&&now.a == 0) { 
    vec.push_back(2); } //3.empty B if (pre.a == now.a&&now.b == 0) { 
    vec.push_back(3); } //4.pour A B if (pre.a > now.a&&pre.b < now.b) { 
    vec.push_back(4); } //5.pour B A if (pre.a < now.a&&pre.b > now.b) { 
    vec.push_back(5); } i++; now = pre; } for (int j = i - 1; j >= 0; j--) { 
    cout << operation[vec[j]] << endl; } cout << "success" << endl; mp.clear(); from.clear(); vec.clear(); } }``` 
小讯
上一篇 2025-02-26 09:50
下一篇 2025-03-05 08:49

相关推荐

版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容,请联系我们,一经查实,本站将立刻删除。
如需转载请保留出处:https://51itzy.com/kjqy/78179.html