Pots POJ 3414

http://poj.org/problem?id=3414

题意： 现给出两个容量分别为 A ，B 的两个杯子， 让你兑出容量为 C 的水。

分析：  现只可能有六种操作， 然后需要一个一个判断，最后递归输出路径

#include<stdio.h>
#include<string.h>
#include<math.h>
#include<queue>
#include<algorithm>
using namespace std;

#define maxn 110

char op[6][20] = {"FILL(1)", "FILL(2)", "DROP(1)", "DROP(2)", "POUR(1,2)", "POUR(2,1)"};

int a, b, c;

/*
  需开出两个结构体，一个开成一维表示两个杯子中的水各是多少，另一个开成二维来存储走过的路径和步数和。
*/
struct node
{
    int x, y, step, k;
} v[maxn][maxn];

struct point
{
  int x, y;
};

void DFS(int p, int q)
{
    if(p == 0 && q == 0)
        return ;

    DFS(v[p][q].x, v[p][q].y);

    printf("%s
", op[v[p][q].k]);
}

void BFS()
{
    point begins, now, next;
    begins.x=begins.y=0;

    queue<point>Q;
    Q.push(begins);
    v[0][0].step = 0;

    while(Q.size())
    {
        now = Q.front();
        Q.pop();

        if(now.x == c || now.y == c)
        {
            printf("%d
", v[now.x][now.y].step);

            DFS(now.x, now.y);
            return ;
        }

        for(int i=0; i<6; i++)
        {
            if(i == 0)
                next.x = a, next.y=now.y;
            else if(i == 1)
                next.y = b, next.x=now.x;
            else if(i == 2)
                next.x = 0, next.y=now.y;
            else if(i == 3)
                next.y = 0, next.x=now.x;
            else if(i == 4)
            {
                 if(now.x+now.y<=b)
                    next.x = 0, next.y=now.x+now.y;
                else
                    next.x = now.x+now.y-b, next.y = b;
            }
            else
            {
                 if(now.x+now.y<=a)
                    next.x = now.x+now.y, next.y=0;
                else
                    next.x = a, next.y = now.x+now.y-a;
            }
            if(v[next.x][next.y].step == 0)
            {
                v[next.x][next.y].k = i;
                 v[next.x][next.y].step = v[now.x][now.y].step + 1;
                v[next.x][next.y].x = now.x;
                v[next.x][next.y].y = now.y;
                Q.push(next);
            }

        }
    }
    printf("impossible
");
}

int main()
{
    memset(v, 0, sizeof(v));
    scanf("%d %d %d", &a, &b, &c);

    BFS();

    return 0;
}