POJ - 3414 Pots 【BFS】

题目链接

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

题意

给出两个杯子 容量分别为 A B 然后给出C 是目标容量

有三种操作

1 将一个杯子装满

2.将一个杯子全都倒掉

3.将一个杯子的水倒到另一个杯子里面

如果某个杯子里面的水 能够达到 目标容量 那么就输出步骤

思路

BFS 并且要存储步骤

每一步一共有六步操作 记得标记

AC代码

#include <cstdio>

#include <cstring>

#include <ctype.h>

#include <cstdlib>

#include <cmath>

#include <climits>

#include <ctime>

#include <iostream>

#include <algorithm>

#include <deque>

#include <vector>

#include <queue>

#include <string>

#include <map>

#include <stack>

#include <set>

#include <numeric>

#include <sstream>

#include <iomanip>

#include <limits>

#define CLR(a) memset(a, 0, sizeof(a))

#define pb push_back

using namespace std;

typedef long long ll;

typedef long double ld;

typedef unsigned long long ull;

typedef pair <int, int> pii;

typedef pair <ll, ll> pll;

typedef pair<string, int> psi;

typedef pair<string, string> pss;

const double PI = acos(-1.0);

const double E = exp(1.0);

const double eps = 1e-8;

const int INF = 0x3f3f3f3f;

const int maxn = 1e2 + 5;

const int MOD = 1e9 + 7;

/*

    0 FILL 1

    1 FILL 2

    2 DROP 1

    3 DROP 2

    4 POUR 1 2

    5 POUR 2 1

*/

int visit[maxn][maxn];

vector <int> ans;

int flag;

int a, b, c;

struct node

{

    int a, b;

    vector <int> v;

};

void bfs()

{

    queue <node> q;

    node tmp;

    tmp.a = 0;

    tmp.b = 0;

    tmp.v.clear();

    q.push(tmp);

    visit[0][0] = 1;

    while (!q.empty())

    {

        node u = q.front(), v;

        q.pop();

        if (u.a == c || u.b == c)

        {

            flag = 1;

            ans = u.v;

            return;

        }

        if (u.a < a)

        {

            v.a = a;

            v.b = u.b;

            if (visit[v.a][v.b] == 0)

            {

                v.v = u.v;

                v.v.pb(0);

                q.push(v);

                visit[v.a][v.b] = 1;

            }

        }

        if (u.b < b)

        {

            v.a = u.a;

            v.b = b;

            if (visit[v.a][v.b] == 0)

            {

                v.v = u.v;

                v.v.pb(1);

                q.push(v);

                visit[v.a][v.b] = 1;

            }

        }

        if (u.a > 0)

        {

            v.a = 0;

            v.b = u.b;

            if (visit[v.a][v.b] == 0)

            {

                v.v = u.v;

                v.v.pb(2);

                q.push(v);

                visit[v.a][v.b] = 1;

            }

        }

        if (u.b > 0)

        {

            v.a = u.a;

            v.b = 0;

            if (visit[v.a][v.b] == 0)

            {

                v.v = u.v;

                v.v.pb(3);

                q.push(v);

                visit[v.a][v.b] = 1;

            }

        }

        if (u.a < a)

        {

            int c = a - u.a;

            if (u.b >= c)

            {

                v.b = u.b - c;

                v.a = a;

            }

            else

            {

                v.b = 0;

                v.a = u.a + u.b;

            }

            if (visit[v.a][v.b] == 0)

            {

                v.v = u.v;

                v.v.pb(5);

                q.push(v);

                visit[v.a][v.b] = 1;

            }

        }

        if (u.b < b)

        {

            int c = b - u.b;

            if (u.a >= c)

            {

                v.a = u.a - c;

                v.b = b;

            }

            else

            {

                v.a = 0;

                v.b = u.a + u.b;

            }

            if (visit[v.a][v.b] == 0)

            {

                v.v = u.v;

                v.v.pb(4);

                q.push(v);

                visit[v.a][v.b] = 1;

            }

        }

    }

}

int main()

{

    map <int, string> M;

    M[0] = "FILL(1)";

    M[1] = "FILL(2)";

    M[2] = "DROP(1)";

    M[3] = "DROP(2)";

    M[4] = "POUR(1,2)";

    M[5] = "POUR(2,1)";

    CLR(visit, 0);

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

    flag = 0;

    bfs();

    if (flag == 0)

        printf("impossible\n");

    else

    {

        int len = ans.size();

        cout << len << endl;

        for (int i = 0; i < len; i++)

            cout << M[ans[i]] << endl;

    }

}