【week2-B】
Pour Water倒水问题
题意:给定容量为A B的两容器,倒来倒去得到容量为C的水
表达:"fill A" 表示倒满A杯,"empty A"表示倒空A杯,"pour A B" 表示把A的水倒到B杯并且把B杯倒满或A倒空。
Input
输入包含多组数据。每组数据输入 A, B, C 数据范围 0 < A <= B 、C <= B <=1000 、A和B互质。
Output
你的程序的输出将由一系列的指令组成。这些输出行将导致任何一个罐子正好包含C单位的水。每组数据的最后一行输出应该是“success”。输出行从第1列开始,不应该有空行或任何尾随空格。
Sample Input
2 7 52 7 4
Sample Output
(步骤可能不唯一合理即可)fill Bpour B Asuccess fill Apour A Bfill Apour A Bsuccess
1、用什么样的数据结构解决?
倒水问题,在找解的过程中,如何把过程关联并存储起来,采用什么样的数据结构,容易联想到结构体可以存储每一个状态,但是,这样的话状态之间的转移关系怎么来实现呢?细想一下,每种状态在特定操作下下一种状态是唯一的,基于此,我们可以联想到这种和链表很相似,不错,我们很自然地采用单链表的思想,在结构体再添加一个实现状态转移记录的指针。
2.算法?bfs怎么用?
框架
典型的 whie(非空) (for .. ) if(符合条件) push
在这里当然也是适用的
我们把起始状态放入到队列里,接着从当前状态可以衍生出至多六种状态,通过判断我们将未曾出现的状态放入队列,大体思路就形成了。
最终状态我们让B到C的状态时结束,返回,输出转移过程即可。
不过值得注意的是我们的链表方向和操作过程是互逆的,怎么办呢,我们把它逆序存到栈里面,然后从栈里出就好了嘛,递归也可,但不想再写函数了,本质也是递归栈,
具体一些细节判断,还需要在实际写的时候琢磨呢在注释里会提到。
//由于最后要求的结果是A B中有一个到达 C 状态,我们不妨让y到达C状态即可 class S{public:int x;int y;int op;S* p;//用来实现状态转移,可以看成 单链表 结构S(int x = 0, int y = 0, int op = 0, S* p = 0):x(x),y(y),op(op),p(p){}bool operator==(int c){return (y == c);}};queue<S*> q;//定义队列,每个表示一种状态并可以记录之后的变化状态int A,B,C;bool hash[1001][1001];void print(int op){switch(op){case 0:cout << "fill A" << endl;break;case 1:cout << "fill B" << endl;break;case 2:cout << "empty A" << endl;break;case 3:cout << "empty B" << endl;break;case 4:cout << "pour A B" << endl;break;case 5:cout << "pour B A" << endl;break;}}S* getState(S *s, int op)//对应操作做状态转移,返回新状态{int x = s->x;int y = s->y;S* ns = 0;switch(op){case 0:// fill 1 A未满---->填满if( x < A ){x = A;ns = new S(x, y, 0, s);}break;case 1:// fill 2B未满----->填满if( y < B ) {y = B;ns = new S(x, y, 1, s);}break;case 2:// drop 1 A非空----->倒空if (x > 0){x = 0;ns = new S(x, y, 2, s);}break;case 3:// drop 2 B非空 -----> 倒空if (y > 0){y = 0;ns = new S(x, y, 3, s);}break;case 4:// pour(1,2) // A-->B可以倒满,倒满B,剩下自己留着if(x > B - y){x = x - (B-y);y = B;ns = new S(x, y, 4, s);} // A--->B倒不满,,全奉献给B,自己空着else if(x>0){y = y + x;x = 0;ns = new S(x, y, 4, s);}break;case 5:// pour(2,1) //大致同case 4 if( y > A - x){y = y - (A-x);x = A;ns= new S(x, y, 5, s);}else if(y > 0){x = x + y;y = 0;ns = new S(x, y, 5, s);}break;}return ns;}void BFS(){int x, y;while(!q.empty())//队列非空时广搜搜起来{S* ps = q.front();//取出来一个状态q.pop();if(*ps == C)//如果到达C状态了{stack<int> st;while(ps->p)//反向寻找中间过程,放入栈中存起来{st.push(ps->op);ps = ps->p;}while(!st.empty())//正向输出状态转移过程{print(st.top());st.pop();}//其实也可以递归。。。cout << "success" << endl;return;} for(int i = 0; i < 6; i++){S *ns = getState(ps, i);// cout << i << (s ? s->x : -1) << (s ? s->y: -1) << endl;//对每一种可能的状态(操作允许且未到达过该状态)if(ns && !hash[ns->x][ns->y]){hash[ns->x][ns->y] = true;//cout << "push(" << ns->x << "," << ns->y <<")" << ns->op << ", " << ns-> p << endl;q.push(ns);}}}}int main(){while(cin >> A >> B >> C){for(int i = 0; i < 1001; i++){for(int j = 0; j < 1001; j++){hash[i][j] = false;}}while(!q.empty()){q.pop();}//清空状态队列hash[0][0] = true;//从其实状态(0,0)开始(A、B都没水)S s(0, 0);q.push(&s);BFS();//广搜开始。。。}return 0; }#include <iostream>#include <queue>#include <stack>using namespace std;