POJ3414 Pots

清疚 2021-11-02 07:34 214阅读 0赞

**题目：**

***给你两个容器，分别能装下A升水和B升水，并且可以进行以下操作***

***FILL(i)        将第i个容器从水龙头里装满(1 ≤ i ≤ 2);***

***DROP(i)        将第i个容器抽干***

***POUR(i,j)      将第i个容器里的水倒入第j个容器（这次操作结束后产生两种结果，一是第j个容器倒满并且第i个容器依旧有剩余，二是第i个容器里的水全部倒入j中，第i个容器为空）***

***现在要求你写一个程序，来找出能使其中任何一个容器里的水恰好有C升，找出最少操作数并给出操作过程***

**输入：**

***有且只有一行，包含3个数A,B,C（1<=A,B<=100,C<=max(A,B)）***

**输出：**

***第一行包含一个数表示最小操作数K***

***随后K行每行给出一次具体操作，如果有多种答案符合最小操作数，输出他们中的任意一种操作过程，如果你不能使两个容器中的任意一个满足恰好C升的话，输出“impossible”***

**样例：**

**![1706379-20190604114835874-39961740.png][]**

**分析：**简单的BFS，难点在于回溯，给每个状态用数组记录路径

#include<iostream>
    #include<sstream>
    #include<cstdio>
    #include<cstdlib>
    #include<string>
    #include<cstring>
    #include<algorithm>
    #include<functional>
    #include<iomanip>
    #include<numeric>
    #include<cmath>
    #include<queue>
    #include<vector>
    #include<set>
    #include<cctype>
    #define PI acos(-1.0)
    const int INF = 0x3f3f3f3f;
    const int NINF = -INF - 1;
    typedef long long ll;
    using namespace std;
    int a, b, c;
    int used[105][105];
    struct node
    {
        int x, y;
        int flag;
        int path[1005];//数组中0-5分别表示6种不同操作
    }st;
    string print[6] = {
        "FILL(1)", "FILL(2)", "DROP(1)", "DROP(2)", "POUR(1,2)", "POUR(2,1)"};
    void bfs()
    {
        queue<node> q;
        for (int i = 0; i <= a; ++i)
        {
            for (int j = 0; j <= b; ++j)
                used[i][j] = INF;
        }
        memset(used, 0, sizeof(used));
        st.x = 0, st.y = 0;
        st.flag = 0;
        memset(st.path, -1, sizeof(st.path));
        q.push(st);
        used[st.x][st.y] = 1;
        while (q.size())
        {
            node temp = q.front();
            q.pop();
            if (temp.x == c || temp.y == c)
            {
                cout << temp.flag << endl;
                for (int i = 0; i < temp.flag; ++i)
                    cout << print[temp.path[i]] << endl;
                return;
            }
            for (int i = 0; i < 6; ++i)
            {
                node now = temp;
                now.flag++;
                if (i == 0 && now.x != a)
                {
                    now.x = a;
                    if (!used[now.x][now.y])
                    {
                        used[now.x][now.y] = 1;
                        now.path[temp.flag] = 0;
                        q.push(now);
                    }
                }
                else if (i == 1 && now.y != b)
                {
                    now.y = b;
                    if (!used[now.x][now.y])
                    {
                        used[now.x][now.y] = 1;
                        now.path[temp.flag] = 1;
                        q.push(now);
                    }
                }
                else if (i == 2 && now.x != 0)
                {
                    now.x = 0;
                    if (!used[now.x][now.y])
                    {
                        used[now.x][now.y] = 1;
                        now.path[temp.flag] = 2;
                        q.push(now);
                    }
                }
                else if (i == 3 && now.y != 0)
                {
                    now.y = 0;
                    if (!used[now.x][now.y])
                    {
                        used[now.x][now.y] = 1;
                        now.path[temp.flag] = 3;
                        q.push(now);
                    }
                }
                else if (i == 4)
                {
                    if (now.x + now.y > b)
                    {
                        now.x -= b - now.y;
                        now.y = b;
                    }
                    else
                    {
                        now.y += now.x;
                        now.x = 0;
                    }
                    if (!used[now.x][now.y])
                    {
                        used[now.x][now.y] = 1;
                        now.path[temp.flag] = 4;
                        q.push(now);
                    }
                }
                else if (i == 5)
                {
                    if (now.x + now.y > a)
                    {
                        now.y -= a - now.x;
                        now.x = a;
                    }
                    else
                    {
                        now.x += now.y;
                        now.y = 0;
                    }
                    if (!used[now.x][now.y])
                    {
                        used[now.x][now.y] = 1;
                        now.path[temp.flag] = 5;
                        q.push(now);
                    }
                }
            }
        }
        cout << "impossible" << endl;
    }
    int main()
    {
        cin >> a >> b >> c;
        bfs();
        return 0;
    }

转载于:https://www.cnblogs.com/veasky/p/10972694.html

[1706379-20190604114835874-39961740.png]: /images/20211102/9342ddaea12549f8b606f2533015ba26.png