题意

倒水问题 “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 5
2 7 4
Sample Output
fill B
pour B A
success
fill A
pour A B
fill A
pour A B
success

思路

根据题意我们知道一共有6种操作：
fill A；
empty A；
pour A B；
fill B；
empty B；
pour B A；
刚开始，我们有两个空杯子，利用上述6种操作，达到至少一个杯子里面含有C单位的水，到这我们似乎没有什么想法。
让我们在想想简单的迷宫路径问题：刚开始从(0,0)点开始，可以向上下左右4个方向中的任意一个没有障碍物的方向移动，然后在此点继续移动，直到到达终点。
可参考利用广度优先遍历搜索BFS在矩阵迷宫中寻找最短路径。
比较一下这两个问题:
A，B两个空杯子——>X，Y位于(0,0)起点
6种操作——>4个方向
A，B中至少一个杯子中含有C单位水——>X，Y位于迷宫终点
我们可以看出，这个问题与迷宫问题比较，就是多了两个操作数以及终点的判断，所以我们可以用迷宫问题模型来接这道题；

过程

整体过程就是将迷宫问题的程序改成此问题的程序:
首先，将迷宫问题中的位置信息数据类型Position改成A，B中水的状态数据类型state；

struct state
{int a;int b;bool operator < (const state &s) const{//注:return a!=s.a?a<s.a:b<s.b;}
};`

让后将迷宫问题的上下左右操作改成倒水的6种操作，详细请看下文代码。
终点的判断改为：

((now.a==C)||(now.b==C))

其余套用迷宫问题代码模板即可；

代码

#include<iostream>
#include<cstdio>
#include<queue>
#include<map>
using namespace std;
struct state
{int a;int b;bool operator < (const state &s) const{return a!=s.a?a<s.a:b<s.b;}
};
queue<state> q;
//队列存储A，B种的各状态 并查找临近状态
//由于本体的输入是多组数据 循环利用队列，所以是全局变量
map<state, state> process;
//与迷宫问题的存储路径类似 下一个状态的内容保存上一个状态
bool judgeState(state &s)
{//类比迷宫问题种判断该点是否访问过以及是否出界，此函数判断A，B中状态是否出现过if(process.find(s)==process.end())  return false;	return true;
}
void print(state &p,int &A,int &B)
{if(p.a==0&&p.b==0){//递归输出 //	printf("%d,%d\n",p.a,p.b);return ;}print(process[p],A,B);string str;//输出操作//判断并输出 由上一状态到下一状态的变化判断操作 输出//process存储的是前一状态 p存储当前状态if(process[p].b==p.b&&process[p].a>p.a&&p.a==0)str="empty A";if(process[p].a==p.a&&p.b==0&&process[p].b>p.b)str="empty B";if(process[p].b==p.b&&process[p].a<p.a&&p.a==A)str="fill A";if(process[p].a==p.a&&process[p].b<p.b&&p.b==B)str="fill B";	if(process[p].a<p.a&&process[p].b>p.b&&(p.a==A||p.b==0))str="pour B A";if(process[p].a>p.a&&process[p].b<p.b&&(p.a==0||p.b==B))str="pour A B";cout<<str<<endl;//printf("%d,%d\n",p.a,p.b);
}
void BFS(int &A,int &B,int &C)
{//套用BFSstate start {0,0};q.push(start);//起点入队列while(!q.empty()){state now=q.front();//获得当前状态(位置）q.pop();//cout<<"----------"<<now.a<<" "<<now.b<<endl;if((now.a==C)||(now.b==C)){//判断最终状态(终点)print(now,A,B);return;}state next;//下一状态(下一位置)//倒满a;if(now.a < A){//若A不为空 则可以执行A倒满操作 B不变next.a=A;next.b=now.b;if(!judgeState(next)){//判断该状态是否到达过(该点是否到达过)process[next]=now;  //存储 下一状态的内容为上一状态q.push(next);  }}//一下操作注释与倒满A类似//倒满b;if(now.b < B){next.b=B;next.a=now.a;if(!judgeState(next)){process[next]=now;q.push(next);}}//倒空a;if(now.a > 0){//A不为空 则可执行A倒空操作 B不变next.a=0;next.b=now.b;if(!judgeState(next)){process[next]=now;q.push(next);}}//倒空b;if(now.b> 0){next.b=0;next.a=now.a;if(!judgeState(next)){process[next]=now;q.push(next);}}//从a倒bif(now.a > 0){//从A倒入B 有两种结果 A被倒空 B被倒满//a空if(now.a+now.b<=B){//a=0 b=a+b B未溢出next.a=0;next.b=now.a+now.b;if(!judgeState(next)){process[next]=now;q.push(next);}}//b满if(now.b!=B) {//B满 A未完  b=B a=A-(B-b)next.a=now.a-(B-now.b);next.b=B;if(!judgeState(next)){process[next]=now;q.push(next);}}}//从b倒aif(now.b > 0){//b空if(now.a+now.b <= A){next.b=0;next.a=now.a+now.b;if(!judgeState(next)){process[next]=now;q.push(next);}}//a满  if(now.a!=A){next.b=now.b-(A-now.a);next.a=A;if(!judgeState(next)){process[next]=now;q.push(next);}}}}
}int main()
{int A,B,C;while(scanf("%d %d %d",&A,&B,&C)!=EOF){process.clear();//每次输入重置状态变化(重置路径)while(!q.empty()) q.pop();  //清空队列BFS(A,B,C);printf("success\n");}return 0;
}

总结

此题与迷宫问题非常相似，套用代码则可轻松解决。
BFS时要注意6种操作的起始和结果状态。输出时也要注意前状态和后状态的比较来判断执行的是什么操作。