這道題目題意很簡單，就是給你兩個容器，求出獲得指定量水的步驟。
一看稍微分析就知道是廣度優先搜索。就是每次最多有六種情況，填滿a，填滿b，清空a，清空b，從a倒到b，從b倒到a。對每種情況將在這種情況下的可能的情況進入隊列，直到找到最終結果。
注意不要以為和題目答案不一樣就以為自己是錯的，因為倒的方法可能不一樣，所以最好自己驗證一下，題目也標出了special judge，就是答案不止一種。
下面是代碼及注釋，注釋的地方就是自己沒關注細節浪費時間的地方。。。。
[cpp]
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define Max(a,b) (a>b?a:b)
#define Min(a,b) (a<b?a:b)
enum METHOD//這裡用了一下枚舉
{
fillA = 0,
fillB,
emptyA,
emptyB,
pourAB,
pourBA
}methods;
struct QUEUE
{
int nowA,nowB;//a，b當前的水量
int method;//上一步是通過什麼方式到這一步的
int pre;//記錄上一步在隊列中的下標
}queue[100000];
int Ca,Cb,N;//輸入
int start, end;//隊列的頭和尾
void output()
{
int step[10000];
int index = 0;
//找到success的整個路徑，倒著找到第一個，放到step數組中
step[index ++] = start;
int k = queue[start].pre;
while (k != -1)
{
step[index ++] = k;
k = queue[k].pre;
}
//輸出，注意queue的下標是step數組，開始寫成i了，怎麼搞都不對。。。。
for (int i = index - 1; i >= 0; -- i)
{
if (queue[step[i]].method == fillA)
{
printf("fill A\n");
}
if (queue[step[i]].method == fillB)
{
printf("fill B\n");
}
if (queue[step[i]].method == emptyA)
{
printf("empty A\n");
}
if (queue[step[i]].method == emptyB)
{
printf("empty B\n");
}
if (queue[step[i]].method == pourAB)
{
printf("pour A B\n");
}
if (queue[step[i]].method == pourBA)
{
printf("pour B A\n");
}
}
printf("success\n");
}
void bfs()
{
start = -1,end = 0;
//初始化隊列，第一步肯定是先填滿A或者B
queue[end].method = fillA;
queue[end].nowA = Ca;
queue[end].nowB = 0;
queue[end].pre = -1;
end ++;
queue[end].method = fillB;
queue[end].nowA = 0;
queue[end].nowB = Cb;
queue[end].pre = -1;
end ++;
//廣度優先搜索
while (start < end)
{
start ++;
if (queue[start].nowB == N || queue[start].nowA == N)//如果A或者B達到最終狀態，那麼隊列結束
{
break;
}
//如果A，B都不是全滿的情況下，可以填充其中一個，因為都滿了沒意義。
if (queue[start].nowA < Ca && queue[start].nowB < Cb)
{
queue[end].method = fillA;
queue[end].nowA = Ca;
queue[end].nowB = queue[start].nowB;
queue[end].pre = start;
end ++;
queue[end].method = fillB;
queue[end].nowA = queue[start].nowA;
queue[end].nowB = Cb;
queue[end].pre = start;
end ++;
}
//如果AB都不是空的情況下，才清空其中一個，因為都空的情況又回到了初始狀態，浪費queue的空間，浪費搜索的時間
if (queue[start].nowA != 0 && queue[start].nowB != 0)
{
queue[end].method = emptyA;
queue[end].nowA = 0;
queue[end].nowB = queue[start].nowB;
queue[end].pre = start;
end ++;
queue[end].method = emptyB;
queue[end].nowA = queue[start].nowA;
queue[end].nowB = 0;
queue[end].pre = start;
end ++;
}
//如果a不為空且B沒有滿，才執行從a向b倒。如果a空了或者b已經滿了，執行這一步沒意義
if (queue[start].nowA != 0 && queue[start].nowB < Cb)
{
if (queue[start].nowA > Cb - queue[start].nowB)
{
queue[end].nowA = queue[start].nowA - Cb + queue[start].nowB;
queue[end].nowB = Cb;
}
else
{
queue[end].nowA = 0;
queue[end].nowB = queue[start].nowB + queue[start].nowA;
}
queue[end].method = pourAB;
queue[end].pre = start;
end ++;
}
//如果b不為空且a沒有滿，才執行從b向a倒。如果b空了或者a已經滿了，執行這一步沒意義
if (queue[start].nowB != 0 && queue[start].nowA < Ca)
{
if (queue[start].nowB > Ca - queue[start].nowA)
{
queue[end].nowB =queue[start].nowB - Ca + queue[start].nowA;
queue[end].nowA = Ca;
}
else
{
queue[end].nowB = 0;
queue[end].nowA = queue[start].nowA + queue[start].nowB;
}
queue[end].method = pourBA;
queue[end].pre = start;
end ++;
}
}
output();
}
int main()
{
while (scanf("%d %d %d", &Ca, &Cb, &N) != EOF)
{
bfs();
}
return 0;
}
