几个杯子倒水的问题

这几乎是一道超经典的智力题（emmmmmm可以这么说，当年面试还被亲身问过这问题）

题目描述

倒水问题 "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列开始，不应该有空行或任何尾随空格。

数据结构与思路

  说到底这还是一道图论的题目，杯子里装载多少水就是几个不同的状态，需要判断的就是状态之间的转移，然后确定的找到一个转移的过程，实现从（0 ，0）到想要的状态。
  恰巧刚刚写了另一个最短路径（记录路径）的问题 迷宫最短路的问题 思路是接近的。就干脆把思路也一起借鉴了过来。

对所有的状态转移都进行考虑（一共六种 1 倒空A 2. 倒空B 3. A倒入B/A被倒空了B不满 4. A倒入B/A未被倒空B满了 5. B倒入A/B被倒空了A不满 4. B倒入A/B未被倒空A满了）对全部六种状态进行判断，然后根据dfs的思路广度优先搜索所有的状态，同时记住自己的前置状态。其中有一个头疼的点就是怎么记住这个点已经被访问过了，我这里选取的办法是定义一个vis[][]数组，大小是两个杯子的两个容量（这样可以清楚的记录是否访问过该点but 会浪费空间，我觉得问题不大）。

搞清楚这一点，基本和迷宫探路思路相同
然后愉快的code 剩下的大致思路参考我的另一个博客迷宫最短路的问题

#include<queue>
#include<iostream>
using namespace std;
//六种变化， A倒空 A倒满 B倒空 B倒满 A倒B B倒A； 
// 0代表起始 
// 1 2 3 4 5 6
struct station
{ 
    int tl;
    int fillerA; 
    int fillerB; //当前状态的容量
    int from; //回溯用的方式 
    int front; //
};
station ap[100000];
int vis[1000][1000];
void display(int k)
{
    if(k==1){ cout<<"empty A"<<endl; }
    else if(k==2){ cout<<"fill A"<<endl; }
    else if(k==3){ cout<<"empty B"<<endl; }
    else if(k==4){ cout<<"fill B"<<endl; }
    else if(k==5){ cout<<"pour A B"<<endl; }
    else if(k==6){ cout<<"pour B A"<<endl; }
}
int main()
{
    int a,b,c;
    cin>>a>>b>>c;
    for (int i = 0; i < 1000; i++)
    {
        for (int j = 0; j < 1000; j++) 
        {
            vis[i][j]=0;
        }
    }
    queue<station> que;
    station x;
    x.tl=0;
    x.fillerA=0;
    x.fillerB=0;
    x.from=0;
    que.push(x);
    ap[0]=x;
    int j;
    int i=1;
    while(!que.empty())
    { 
        station p=que.front();
        que.pop();
        if(p.fillerA==c||p.fillerB==c)
        {
            j=p.tl;
            break;
        }
        //empty A
        if(p.fillerA!=0&&!vis[0][p.fillerB])
        {
            station x1;
            x1.fillerA=0;
            x1.fillerB=p.fillerB;
            x1.from=1;
            x1.front=p.tl;
            x1.tl=i;
            ap[i]=x1;
            vis[0][p.fillerB]=1;
            que.push(x1);
            i++;
        }
        //fill A
        if(p.fillerA!=a&&!vis[a][p.fillerB])
        {
            station x1;
            x1.fillerA=a;
            x1.fillerB=p.fillerB;
            x1.from=2;
            x1.front=p.tl;
            x1.tl=i;
            ap[i]=x1;
            vis[a][p.fillerB]=1;
            que.push(x1);
            i++;
        }
        //empty B
        if(p.fillerB!=0&&!vis[p.fillerA][0])
        {
            station x1;
            x1.fillerA=p.fillerA;
            x1.fillerB=0;
            x1.from=3;
            x1.front=p.tl;
            x1.tl=i;
            ap[i]=x1;
            vis[p.fillerA][0]=1;
            que.push(x1);
            i++;
        }
        //fill B
        if(p.fillerB!=b&&!vis[p.fillerA][b])
        {
            station x1;
            x1.fillerA=p.fillerA;
            x1.fillerB=b;
            x1.from=4;
            x1.front=p.tl;
            x1.tl=i;
            ap[i]=x1;
            vis[p.fillerA][b]=1;
            que.push(x1);
            i++;
        }
        //A 倒入B
        //倒空A或者倒满B 
        //倒满B 
        if(p.fillerA>=(b-p.fillerB)&&!vis[p.fillerA-b+p.fillerB][b])
        {
            station x1;
            x1.fillerA=p.fillerA+p.fillerB-b;
            x1.fillerB=b;
            x1.from=5;
            x1.front=p.tl;
            x1.tl=i;
            ap[i]=x1;
            vis[p.fillerA+p.fillerB-b][b]=1;
            que.push(x1);
            i++;
        }
        //倒空 A 
        if(p.fillerA<(b-p.fillerB)&&!vis[0][p.fillerA+p.fillerB])
        {
            station x1;
            x1.fillerA=0;
            x1.fillerB=p.fillerA+p.fillerB;
            x1.from=5;
            x1.front=p.tl;
            x1.tl=i;
            ap[i]=x1;
            vis[0][p.fillerA+p.fillerB]=1;
            que.push(x1);
            i++;
        }
        //B 倒入A
        //倒空B或者倒满A
        //倒满A 
        if(p.fillerB>=(b-p.fillerA)&&!vis[a][p.fillerA+p.fillerB-a])
        {
            station x1;
            x1.fillerA=a;
            x1.fillerB=p.fillerA+p.fillerB-a;
            x1.from=6;
            x1.front=p.tl;
            x1.tl=i;
            ap[i]=x1;
            vis[a][p.fillerA+p.fillerB-a]=1;
            que.push(x1);
            i++;
        }
        //倒空 B
        if(p.fillerB<(b-p.fillerA)&&!vis[p.fillerA+p.fillerB][0])
        {
            station x1;
            x1.fillerA=p.fillerA+p.fillerB;
            x1.fillerB=0;
            x1.from=6;
            x1.front=p.tl;
            x1.tl=i;
            ap[i]=x1;
            vis[p.fillerA+p.fillerB][0]=1;
            que.push(x1);
            i++;
        }
    }
    station al[1000];
    station p=ap[j];
    int k=j;
    int k1=0;
    while(p.from!=0)
    {
        al[k1]=p;
        p=ap[p.front];
        
        k1++;
    } 
    for(int t=k1;t>=0;t--)
    {
        display(al[t].from);
    }
    return 0;
}