题意:倒水问题,现在有两个容积为a和b的水壶,对每个水壶可以进行4种操作,两个水壶之间相互倒水(一个水壶倒空或者一个水壶倒满为止),从水农头那里灌水(将水壶灌满为止),向外倒水(将水壶倒空为止),问对这两个水壶进行这样的一系列操作是否可以量出容积为c的水(两个杯子中有一个水壶中的水的容积恰好为c)
     这里添加一个水壶编号为0,容积为a和b的水壶分别编号为1和2,编号为0的水壶的容积置为a+b(保证0号水壶可以向1或2中加水,或者1或2向0中加水),再用BFS来进行求解.
#include<iostream>
#include<string>
#include<cstdlib>
#include<algorithm>
using namespace std;

const int MAXN=105;

int cap[3],result;                                                                                 //水壶的容量以及{zh1}水的体积
int vis[MAXN][MAXN];

struct Node
{
int v[3];                                                                                  //存储3个水壶中所盛水的体积
int fa;
}q[MAXN*MAXN];

Node path[MAXN*MAXN];

void print_path(int ans)                                                                          //打印操作
{
int i=0,j,k;
Node p1,p2;
while(q[ans].fa!=ans)
{
   path[i++]=q[ans];
   ans=q[ans].fa;
}
path[i]=q[ans];
while(i>=1)
{
   p1=path[i];
   p2=path[--i];
   if(p1.v[0]==p2.v[0])                                                             //这里用编号为0的水壶中前后两个状态的水的体积变化来作为判断标准
   {
    if(p1.v[1]<p2.v[1])
     printf("pour B A\n");
    else
     printf("pour A B\n");
   }
   else if(p1.v[0]!=p2.v[0])
   {
    for(j=1;j<3;j++)
    if(p1.v[j]==p2.v[j])
     break;
    k=3-j;
    if(p1.v[k]<p2.v[k])
     printf("fill %c\n",k-1+'A');
    else
     printf("empty %c\n",k-1+'A');
   }
}
printf("success\n");
}

void BFS()
{
int i,j,k,amount,front=0,rear=1;
q[0].v[0]=cap[0];                        
q[0].v[1]=q[0].v[2]=q[0].fa=0;
vis[0][0]=1;
while(front<rear)
{
   Node & u=q[front];
   if(u.v[1]==result||u.v[2]==result)                           //到达目标状态,打印方案
   {
    print_path(front);
    return;
   }
   for(i=0;i<3;i++)                                                      //编号为i的水壶向编号为j的水壶中倒水
   for(j=0;j<3;j++)
    if(i!=j)
    {
     Node & v=q[rear];
     if(u.v[i]<cap[j]-u.v[j])
      amount=u.v[i];                                                  //amount便是本次操作可以倒出的水量
     else
      amount=cap[j]-u.v[j];
     for(k=0;k<3;k++)                                              
      v.v[k]=u.v[k];                                                  //扩展新节点
     v.v[i]-=amount;                                                //倒出
     v.v[j]+=amount;                                                //倒进
     if(!vis[v.v[1]][v.v[2]])
     {
      vis[v.v[1]][v.v[2]]=1;                                       //标记为已经访问
      v.fa=front;
      rear++;
     }
    }
   front++;
}
}

int main()
{
while(scanf("%d%d%d",&cap[1],&cap[2],&result)!=EOF)
{
   cap[0]=cap[1]+cap[2];
   memset(vis,0,sizeof(vis));
   BFS();
}
system("pause");
return 0;
}