POJ 3414 得到想要的容量 BFS

题目的大意是：给你两个容量固定的烧杯，容量分别是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:
                {
        &nbs

补充：软件开发 , C++ ,