bfs解决倒水问题

【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的状态时结束，返回，输出转移过程即可。

不过值得注意的是我们的链表方向和操作过程是互逆的，怎么办呢，我们把它逆序存到栈里面，然后从栈里出就好了嘛，递归也可，但不想再写函数了，本质也是递归栈，

具体一些细节判断，还需要在实际写的时候琢磨呢在注释里会提到。

#include <iostream>#include <queue>#include <stack>using namespace std;

//由于最后要求的结果是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; }