題目的大意是： 給你兩個容量固定的燒杯，容量分別是A和B，如何得到體積是C的水，只有如下操作是合法的
1. 裝滿A，從水源處獲得
2. 裝滿B
3, 將A倒給B，倒完後或者B倒滿了，或者A空了
4. 將B倒給A，倒完後或者A滿了，或者B空了
5. 將A清空
6. 將B清空
求出最少的步驟可以使得從最初兩個空杯，得到體積為C水，其中容量為C的水，可以放在任何一個容器中。
Sample Input
3 5 4
Sample Output
6
FILL(2)
POUR(2,1)
DROP(1)
POUR(2,1)
FILL(2)
POUR(2,1)
分析：此題的分類是BFS，不過自己想半天也沒有想清楚如何BFS，看了discussion裡的一些提示，才所有頓悟。
在BFS的過程中，當前的狀態是兩個數，ca，cb，描述當前a燒杯中有水ca，b燒杯中有水cb。
因為下一步只有六種選擇的情況，所以我們把這六個情況都枚舉出來，例如當權枚舉到stepi，如果經過這一步的操作，達到的狀態出現過，我們就不將新狀態放入隊列，
否則作為新的狀態放入隊列。
我們要記錄路徑，所以還要保留每個狀態之前的狀態，同時也有保存到達當前狀態的時候，經歷了多少步。
所以每個狀態裡面的有如下值：
1. 兩個燒杯的容量 2. 前一個狀態 3.到當前狀態步驟 4 到這個狀態所采用的操作。
代碼如下：
[cpp]
#include <stdio.h>
#include <memory.h>
#define MAX_NUM 101
#define MAX_Q MAX_NUM * MAX_NUM
enum OPERATION
{
FILL1 = 0, FILL2, POUR12, POUR21, DROP1, DROP2, NONE
};
struct Step
{
int liter1;
int liter2;
int stepID;
OPERATION operation;
int previous;
Step()
{
}
Step(int l1, int l2, int step, OPERATION op, int previous)
{
liter1 = l1;
liter2 = l2;
stepID = step;
operation = op;
this->previous = previous;
}
};
struct Queue
{
Step steps[MAX_Q];
int front;
int rear;
void ini()
{
memset(steps, 0, sizeof(steps));
front = rear = 0;
}
void push(int l1, int l2, int step, int privous, OPERATION op)
{
steps[rear++] = Step(l1, l2, step, op, privous);
}
};
bool visit[MAX_NUM][MAX_NUM];
Queue q;
void PrintPath(int i)
{
if( i == -1)
{
return ;
}
PrintPath(q.steps[i].previous);
switch(q.steps[i].operation)
{
case FILL1:
printf("FILL(1)\n");
break;
case FILL2:
printf("FILL(2)\n");
break;
case POUR12:
printf("POUR(1,2)\n");
break;
case POUR21:
printf("POUR(2,1)\n");
break;
case DROP1:
printf("DROP(1)\n");
break;
case DROP2:
printf("DROP(2)\n");
break;
}
}
void BFS(int a, int b, int c)
{
q.ini();
q.push(0, 0, 0, -1, NONE);
visit[0][0] = true;
Step nxt,current;
while(q.rear > q.front)
{
current = q.steps[q.front++];
if(current.liter1 == c || current.liter2 == c)
{
break;
}
OPERATION iOp;
for( int i = 0; i < 6; i++)
{
iOp = (OPERATION)i;
nxt = current;
switch(iOp)
{
case FILL1:
{
//fill glass a
if( !visit[a][nxt.liter2] )
{
q.push(a, nxt.liter2, current.stepID + 1, q.front - 1, FILL1);
visit[a][nxt.liter2] = true;
}
break;
}
case FILL2:
{
if( !visit[nxt.liter1][b] )
{
q.push(nxt.liter1, b, current.stepID + 1, q.front - 1, FILL2);
visit[nxt.liter1][b] = true;
}
break;
}
case POUR12:
{
int newA = current.liter1;
int newB = current.liter2;
if(newA + newB > b)
{
newA = newA + newB - b;
newB = b;
}
else
{
newB = newA + newB;
newA = 0;
}
if(!visit[newA][newB])
{
q.push(newA, newB, current.stepID + 1, q.front - 1, POUR12);
visit[newA][newB] = true;
}
break;
}
case POUR21:
{
int newA = current.liter1;
int newB = current.liter2;
if(newA + newB > a)
{
newB = newA + newB - a;
newA = a;
}
else
{
newA = newA + newB;
newB = 0;
}
if(!visit[newA][newB])
{
q.push(newA, newB, current.stepID + 1, q.front - 1, POUR21);
visit[newA][newB] = true;
}
break;
}
case DROP1:
{
if( !visit[0][nxt.liter2] )
{
q.push(0, nxt.liter2, current.stepID + 1, q.front - 1, DROP1);
visit[0][nxt.liter2] = true;
}
break;
}
case DROP2:
{
if( !visit[nxt.liter1][0] )
{
q.push(nxt.liter1, 0, current.stepID + 1, q.front - 1, DROP2);
visit[nxt.liter1][0] = true;
}
break;
}
}
}
}
if( q.front == q.rear)
{
printf("impossible\n");
}
else
{
printf("%d\n", q.steps[q.front-1].stepID);
PrintPath(q.front-1);
}
}
int main()
{
int a,b,c;
while(scanf("%d%d%d", &a, &b, &c) != EOF)
{
memset(visit, 0, sizeof(visit));
BFS(a, b, c);
}
return 0;
}
編寫的時候犯了好幾個bug，導致半天都調不通
bug1， 在newA newB賦值的時候，將順序寫錯，忽略了兩個值存在依賴關系的事實。
bug2， 最後遍歷的時候，沒有寫front-1， 其實front在上次取完了的時候，就已經-1.
