题意:
有无限量的水,以及容量为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(); } }```

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