poj-3414-Pots(BFS路径输出)

发布于 2019-07-23  935 次阅读


问题传送门:

题意:

已知两个空桶的容量,有三种操作。
1.把桶加满
2.把桶倒空
3.把A中的水尽可能多得加到B中

问最少操作多少次,使任意一个桶中的水达到 C

分析:

一个桶有三种操作,也就是 一个桶可以演变出三种状态,两个桶就是有六种状态。
可以用BFS,把每一种状态加入到一个优先队列中,优先队列按照操作步数升序维护。

每次取优先队列的第一个状态,去判断它所能达到的六种状态!!!

再用一个vis数字标记某一组状态是否出现过,如果没有出现过就加入到队列,
如果出现过,不需要加入,继续判断之后的状态。
如果所有的状态都出现了,并且优先队列为空了,那么就是“impossible”,
如果其中一个队列满足要求,这时就需要输入路径,,,

-----路径的输出-----
每一个状态维护一个到达这个状态所进行的操作顺序,
这样,当到终点的时候,就能直接输出路径
详细请看代码:

代码:

#include <iostream>
#include <queue>

using namespace std;

const int MAXN = 110;
int A, B, C;
int vis[MAXN][MAXN];
string path[MAXN] = {"FILL(1)","FILL(2)",
                     "DROP(1)","DROP(2)",
                     "POUR(1,2)","POUR(2,1)"};队列


struct Node
{
    int a, b, step;
    queue<int>p;
} t, nx;

struct cmp
{
    bool operator ()(Node &a, Node &b)
    {
        return a.step > b.step;
    }
};

priority_queue<Node, vector<Node>, cmp> q;

void BFS()
{
    t.a = 0, t.b = 0, t.step = 0;
    vis[0][0] = 1;
    q.push(t);
    while(!q.empty())
    {
        t = q.top();
        q.pop();
        nx.step = t.step + 1;
        for (int i = 0; i < 6; i++)
        {
            if (i == 0 && t.a != A) { //填满A
                nx.a = A;
                nx.b = t.b;
                nx.p=t.p;
                nx.p.push(0);
            } else if(i == 1 && t.b != B) { //填满B
                nx.b = B;
                nx.a = t.a;
                nx.p=t.p;
                nx.p.push(1);
            } else if (i == 2 && t.a != 0){ //抽干A
                nx.a = 0;
                nx.b = t.b;
                nx.p=t.p;
                nx.p.push(2);
            } else if (i == 3 && t.b != 0){ //抽干B
                nx.a = t.a;
                nx.b = 0;
                nx.p=t.p;
                nx.p.push(3);
            }else if(i==4&&t.a!=0&&t.b!=B){ //A->B
                if (t.a+t.b > B)
                    nx.b=B, nx.a=t.a+t.b-B;
                else
                    nx.a=0, nx.b=t.a+t.b;
                nx.p=t.p;
                nx.p.push(4);
            } else if(i==5&&t.a!=A&&t.b!=0){//B->A
                
                if (t.a+t.b > A)
                    nx.a = A, nx.b = t.a+t.b-A;
                else
                    nx.b = 0, nx.a = t.a+t.b;
                nx.p=t.p;
                nx.p.push(5);
            }else
                continue;
            
            // -------
            if (vis[nx.a][nx.b]) continue;
            //cout << nx.a <<" "<<nx.b<<" "<<nx.step<< endl;
            if (nx.a == C || nx.b == C)
            {
                cout << nx.step << endl;
                while (!nx.p.empty()) {
                    cout << path[nx.p.front()] << endl;
                    nx.p.pop();
                    
                }
                return;      
            }
            vis[nx.a][nx.b] = 1; 
            q.push(nx);
        }
    }
    cout << "impossible" << endl;
    return ;
}

int main()
{
    cin >> A >> B >> C;
    BFS();
    
    return 0;
}

Simple And Clear