广搜，路径输出
题目意思：
给出两个壶的容量A和B, 一个目标水量C，对A、B可以有３种操作，求最少经过几步操作能够在某个壶中得到目标水量C。
输入A、B和C，输入最少操作数和操作过程。 题目 和 poj 3414 一样。
本题要点：
1、状态表示：
把A和B壶中水量作为状态，初始状态为<0,0>，每个操作都是状态变化的过程。因为有２个壶，所以总共有６种操作。
vis[i][j] 表示第一个水杯装i， 第二个水杯装j 的状态是否出现过。
2、用广搜，搜索可能出现的状态， 如果 存在某个状态，a水杯或者b水杯的水量 等于 c，说明存在一定的步骤。否则 impossible。
某种个状态 node f 的下一个状态，可能向 6 种操作发展
#include <cstdio>
#include <cstring>
#include <string>
#include <queue>
#include <iostream>
using namespace std;
const int MaxN = 110;
int a, b, c;
bool vis[MaxN][MaxN]; //vis[i][j] 表示第一个水杯装i， 第二个水杯装j 的状态是否出现过struct node
{
int a, b, level; //level 表示这个状态是第几次入队列的char path[MaxN];int pre; //pre 表示path 最后一个元素的下标
};string path[] = {
"fill A", "fill B", "empty A", "empty B", "pour A B", "pour B A"};void print_res(char p[], int n)
{
for(int i = 0; i < n; ++i){
printf("%s\n", path[(int)p[i]].c_str());}printf("success\n");
}void bfs()
{
queue<node> q;memset(vis, false, sizeof vis);node f;f.a = 0, f.b = 0, f.level = 0, f.pre = 0;memset(f.path, 0, sizeof f.path);q.push(f);vis[f.a][f.b] = true;while(!q.empty()){
f = q.front();q.pop();if(f.a == c ||f.b == c){
print_res(f.path, f.pre); return;}node v = f;v.level++;v.pre++;if(a > f.a) // fill A{
v.a = a, v.b = f.b;if(!vis[v.a][v.b]){
v.path[f.pre] = 0;q.push(v);vis[v.a][v.b] = true;}}if(b > f.b) // fill B{
v.a = f.a, v.b = b;if(!vis[v.a][v.b]){
v.path[f.pre] = 1;q.push(v);vis[v.a][v.b] = true;}}if(f.a) // empty A{
v.a = 0, v.b = f.b;if(!vis[v.a][v.b]){
v.path[f.pre] = 2;q.push(v);vis[v.a][v.b] = true;}}if(f.b) // empty B{
v.a = f.a, v.b = 0;if(!vis[v.a][v.b]){
v.path[f.pre] = 3;q.push(v);vis[v.a][v.b] = true;}}if(f.a && f.b < b) // pour A B{
if(f.a > (b - f.b)) //a 能装满 b{
v.a = f.a - (b - f.b);v.b = b;}else{
v.a = 0;v.b = f.b + f.a;}if(!vis[v.a][v.b]){
v.path[f.pre] = 4;q.push(v);vis[v.a][v.b] = true;}}if(f.b && f.a < a) // pour B A{
if(f.b > (a - f.a)){
v.a = a;v.b = f.b - (a -f.a);}else{
v.a = f.a + f.b;v.b = 0;}if(!vis[v.a][v.b]){
v.path[f.pre] = 5;q.push(v);vis[v.a][v.b] = true;}}}
}int main()
{
while(scanf("%d%d%d", &a, &b, &c) != EOF){
bfs();}return 0;
}/* 3 5 4 5 7 3 *//* fill B pour B A empty A pour B A fill B pour B A success fill A pour A B fill A pour A B empty B pour A B success */