POJ3414 Pots BFS搜素

题意：通过题目给出的三种操作，让任意一个杯子中的水到达一定量

分析：两个杯子最大容量是100，所以开个100*100的数组记录状态，最多1w个状态，所以复杂度很低，然后记录一下路径就好

注：代码写残了，我也不会写好看的那种，罪过罪过..QAQ

#include<cstdio>

#include<algorithm>

#include<iostream>

#include<cstring>

#include<cmath>

#include<map>

#include<queue>

#include<stdlib.h>

#include<string>

#include<set>

using namespace std;

typedef long long LL;

const int maxn=;

const int INF=0x3f3f3f3f;

struct Point

{

    int x,y,op,s;

} mp[maxn][maxn],o,t;

int p[maxn][maxn];

queue<Point>q;

void print(int x,int y)

{

    if(x==-)return;

    print(mp[x][y].x,mp[x][y].y);

    if(mp[x][y].op==)printf("FILL(%d)\n",mp[x][y].s);

    else if(mp[x][y].op==)printf("DROP(%d)\n",mp[x][y].s);

    else if(mp[x][y].op==)printf("POUR(%d,%d)\n",mp[x][y].s,-mp[x][y].s);

}

int main()

{

    int a,b,c,flag=;

    scanf("%d%d%d",&a,&b,&c);

    for(int i=; i<=a; ++i)

        for(int j=; j<=b; ++j)

            mp[i][j].op=-;

    mp[a][].op=,mp[a][].s=;

    mp[][b].op=,mp[][b].s=;

    mp[a][].x=-,mp[][b].x=-;

    o.x=a,o.y=;

    q.push(o);

    o.x=,o.y=b;

    q.push(o);

    p[a][]=p[][b]=;

    while(!q.empty())

    {

        o=q.front();

        q.pop();

        if(o.x==c||o.y==c)

        {

            t=o;

            flag=;

            break;

        }

        if(o.x<a)

        {

            if(mp[a][o.y].op==-)

            {

                mp[a][o.y].op=;

                mp[a][o.y].s=;

                mp[a][o.y].x=o.x;

                mp[a][o.y].y=o.y;

                t.x=a,t.y=o.y;

                p[t.x][t.y]=p[o.x][o.y]+;

                q.push(t);

            }

        }

        if(o.y<b)

        {

            if(mp[o.x][b].op==-)

            {

                mp[o.x][b].op=;

                mp[o.x][b].s=;

                mp[o.x][b].x=o.x;

                mp[o.x][b].y=o.y;

                t.x=o.x,t.y=b;

                 p[t.x][t.y]=p[o.x][o.y]+;

                q.push(t);

            }

        }

        if(o.x)

        {

            if(mp[][o.y].op==-)

            {

                mp[][o.y].op=;

                mp[][o.y].s=;

                mp[][o.y].x=o.x;

                mp[][o.y].y=o.y;

                t.x=,t.y=o.y;

                 p[t.x][t.y]=p[o.x][o.y]+;

                q.push(t);

            }

            int cha=b-o.y;

            if(o.x<=cha)

                t.y=o.y+o.x,t.x=;

            else t.y=b,t.x=o.x-cha;

            if(mp[t.x][t.y].op==-)

            {

                mp[t.x][t.y].op=;

                mp[t.x][t.y].s=;

                mp[t.x][t.y].x=o.x;

                mp[t.x][t.y].y=o.y;

                 p[t.x][t.y]=p[o.x][o.y]+;

                q.push(t);

            }

        }

        if(o.y)

        {

            if(mp[o.x][].op==-)

            {

                mp[o.x][].op=;

                mp[o.x][].s=;

                mp[o.x][].x=o.x;

                mp[o.x][].y=o.y;

                t.x=o.x,t.y=;

                 p[t.x][t.y]=p[o.x][o.y]+;

                q.push(t);

            }

            int cha=a-o.x;

            if(o.y<=cha)

                t.x=o.y+o.x,t.y=;

            else t.x=a,t.y=o.y-cha;

            if(mp[t.x][t.y].op==-)

            {

                mp[t.x][t.y].op=;

                mp[t.x][t.y].s=;

                mp[t.x][t.y].x=o.x;

                mp[t.x][t.y].y=o.y;

                 p[t.x][t.y]=p[o.x][o.y]+;

                q.push(t);

            }

        }

    }

    if(flag)printf("%d\n",p[t.x][t.y]),print(t.x,t.y);

    else printf("impossible\n");

    return ;

}