程式設計思維與實踐 Week2 作業 B - Pour Wate

題目描述：

倒水問題 "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列開始，不應該有空行或任何尾随空格。

思路：

這不是一道圖論的題目，但是可以通過廣度優先搜尋的方法來解決。在已知目前A B兩個杯子的狀态後，可以選擇下一個狀态，但是下一個狀态應該是之前沒有出現過的，否則将進入死循環，這樣沒有任何意義。是以，廣度優先搜尋的思路就形成了，首先确定初始狀态：A滿B空或者A空B滿，将兩個狀态分别進隊，然後開始搜尋即可，在出現A或B杯中的水量為C時，搜尋停止。

總結：

AC代碼：

#include<iostream>
#include<cstdio>
#include<cstring>
#include<queue>
using namespace std;
bool flag[1010][1010];
int ansa[1010][1010],ansb[1010][1010],outa[10100],outb[10100],sum;
int A,B,C;
string s[5000];
struct node
{
  int a;
  int b;
}x;
queue<node> q;
void out()
{
  int a,b,nexta,nextb;
  for(int i=sum;i>1;i--)
  {
    if(i==sum)
    {
      if(outa[i]==A)
      cout<<"fill A"<<endl; 
      else
      cout<<"fill B"<<endl;
      //continue; 
    }
    a=outa[i],b=outb[i];
    nexta=outa[i-1],nextb=outb[i-1];
    if(nexta!=a&&nextb!=b)
    {
      if(nexta==0||nextb==B)
      cout<<"pour A B"<<endl;
      else cout<<"pour B A"<<endl;
    }
    else if(nexta==a&&nextb!=b)
    {
      if(nextb==0)
      cout<<"empty B"<<endl;
      else cout<<"fill B"<<endl;
    }
    else
    {
      if(nexta==0)
      cout<<"empty A"<<endl;
      else cout<<"fill A"<<endl;
    }
  }
  cout<<"success"<<endl;
}
void output(int a,int b)
{
  int lasta,lastb;sum=0;
  while(1)
  {
    int t=a;
    outa[++sum]=a;
    outb[sum]=b;
    a=ansa[a][b];
    b=ansb[t][b];//擷取上次狀态 
    if(a==A&&b==0)
    {
      outa[++sum]=A;
      outb[sum]=0;
      break;
    }
    if(a==0&&b==B)
    {
      outa[++sum]=0;
      outb[sum]=B;
      break;
    }
  }
  out();
}
void bfs()
{
  while(!q.empty()) q.pop();
  memset(ansa,0,sizeof(ansa)); 
  memset(ansb,0,sizeof(ansb)); 
  memset(flag,0,sizeof(flag));
  x.a=A;
  x.b=0;
  flag[A][0]=1;
  q.push(x);
  x.a=0;
  x.b=B;
  flag[0][B]=1;
  q.push(x);
  while(!q.empty())
  {
    int nowa=q.front().a;
    int nowb=q.front().b;
    q.pop();node tmp;
    if(nowa==C||nowb==C)
    {
      output(nowa,nowb);
      return;
    }
    if(nowa!=A)//a可以倒滿 
    {
      tmp.a=A;tmp.b=nowb;
      if(!flag[tmp.a][tmp.b])
      {
        ansa[tmp.a][tmp.b]=nowa;
        ansb[tmp.a][tmp.b]=nowb;
        flag[tmp.a][tmp.b]=1;
        q.push(tmp);
      }
    }
    if(nowa!=A&&nowb>0)//b往a中倒
    {
      int cha=A-nowa;
      if(cha>nowb)//b倒入a且a還不滿
      {
        tmp.a=nowa+nowb;
        tmp.b=0;
        if(!flag[tmp.a][tmp.b])
        {
          ansa[tmp.a][tmp.b]=nowa;
          ansb[tmp.a][tmp.b]=nowb;
          flag[tmp.a][tmp.b]=1;
          q.push(tmp);
        }
      }
      else//b倒入a，a滿 
      {
        tmp.a=A;
        tmp.b=nowb-cha;
        if(!flag[tmp.a][tmp.b])
        {
          ansa[tmp.a][tmp.b]=nowa;
          ansb[tmp.a][tmp.b]=nowb;
          flag[tmp.a][tmp.b]=1;
          q.push(tmp);
        }
      }
    }
    if(nowb!=B)//将b倒滿 
    {
      tmp.a=nowa;tmp.b=B;
      if(!flag[tmp.a][tmp.b])//将b倒滿 
      {
        ansa[tmp.a][tmp.b]=nowa;
        ansb[tmp.a][tmp.b]=nowb;
        flag[tmp.a][tmp.b]=1;
        q.push(tmp);
      }
    }
    if(nowa>0&&nowb!=B)//a往b中倒 
    {
      int cha=B-nowb;
      if(nowa<cha)//a倒入b後，a空
      {
        tmp.a=0;
        tmp.b=nowb+nowa;
        if(!flag[tmp.a][tmp.b])
        {
          ansa[tmp.a][tmp.b]=nowa;
          ansb[tmp.a][tmp.b]=nowb;
          flag[tmp.a][tmp.b]=1;
          q.push(tmp);
        }
      }
      else//a倒入b後，b滿 
      {
        tmp.a=nowa-cha;
        tmp.b=B;
        if(!flag[tmp.a][tmp.b])
        {
          ansa[tmp.a][tmp.b]=nowa;
          ansb[tmp.a][tmp.b]=nowb;
          flag[tmp.a][tmp.b]=1;
          q.push(tmp);
        }
      }
    }
    if(nowa>0)//a倒空 
    {
      tmp.a=0;tmp.b=nowb;
      if(!flag[tmp.a][tmp.b])
      {
        ansa[tmp.a][tmp.b]=nowa;
        ansb[tmp.a][tmp.b]=nowb;
        flag[tmp.a][tmp.b]=1;
        q.push(tmp);
      }
    }
    if(nowb>0)//b倒空 
    {
      tmp.a=nowa;tmp.b=0;
      if(!flag[tmp.a][tmp.b])
      {
        ansa[tmp.a][tmp.b]=nowa;
        ansb[tmp.a][tmp.b]=nowb;
        flag[tmp.a][tmp.b]=1;
        q.push(tmp);
      }
    }
  }
}
int main()
{
  while(scanf("%d%d%d",&A,&B,&C)!=EOF)
  {
    if(A==C)
    {
      cout<<"fill A"<<endl<<"success"<<endl;
      continue;
    }
    else if(B==C)
    {
      cout<<"fill B"<<endl<<"success"<<endl;
      continue;
    }
    bfs();
  }
}