POJ 3414 - Pots


问题描述

给出了两个瓶子的容量A,B, 以及一个目标水量C,

对A、B可以有如下操作:

  • FILL(i): fill the pot i (1 ≤ i ≤ 2) from the tap;
  • DROP(i): empty the pot i to the drain;
  • POUR(i,j): pour from pot i to pot j; after this operation either the pot j is full (and there may be some water left in the pot i), or the pot i is empty (and all its contents have been moved to the pot j).

问经过哪几个操作后能使得任意一个瓶子的残余水量为C。

若不可能得到则输出impossible

解题思路

6入口的BFS

把两个两个桶的某个同一时间的状态看做一个整体,视为初态

可对初态进行六种操作,即 FILL(1), FILL(2), DROP(1), DROP(2), POUR(1,2), POUR(2,1)

这6种操作在我的程序中分别用一个整数进行记录:

  • 1z0: 清空z瓶子
  • 2z0: 装满z瓶子
  • 3xy: 从x瓶倒向y瓶

x,y,z∈{1,2}

这样在输出操作时就能根据数字的特点 进行选择性输出 了


这题有两个难点

第一就是要输出得到容量C的过程

对于BFS的题而言这种要求是非常刁钻的,回溯每一步时很容易就混淆了下标。

解决方法:对于每一步的操作,我们都得对它设置一个pos指针,使它指向前一步操作在 queue[] 队列的下标,即对下标进行回溯,再顺序输出每一步操作。

第二就是状态记录

怎样记录两个瓶子在同一时间点的状态,又能使得搜索标记时为O(1)的复杂度?

瓶子某时刻的残余水量就是该瓶子的状态,设残余水量为k1 k2

开始时我想对k1 k2进行各种运算组合,但都无法保证k1 k2的运算组合是独一无二的。

最后我决定用 ostringstream 在k1 k2 两个数字之间加上一个逗号,把他们变为字符串string,再利用map进行标记,相当成功。


最后我简单说说各种操作的数学表达式

设1瓶的容量为v1,残余水量为k1, 2瓶的容量为v2,残余水量为 k2 , 那么:

  • fill(1) 相当于 k1=v1
  • fill(2) 相当于 k2=v2
  • drop(1) 相当于 k1=0
  • drop(2) 相当于 k2=0
  • 对于 Pour(1,2)

      若 k1+k2<=v2,则 k2=k1+k2k1=0 (有先后顺序)

      否则 k1=k1+k2-v2k2=v2 (有先后顺序)
  • Pour(2,1) 亦同理

AC 源码

//Memory Time
//232K   32MS 

#include<iostream>
#include<string>
#include<sstream>
#include<map>
using namespace std;

int v1,v2;  //两个瓶子的容量
int c;      //目标残余水量

int k1,k2;  //在某状态时两个瓶子的剩余水量,temporary

typedef class
{
    public:
        int x,y; //当前状态(两个瓶子中的水量)
        int pos;  //记录前一状态在队列queue中的下标
        int step;  //当前步数
}process;

//把整数a、b整合为 "a,b"  的字符串形式(不包括引号),用于标记状态
string combAB(int a,int b)
{
    string s;
    ostringstream oss;

    oss<<a;
    oss<<',';
    oss<<b;

    s=oss.str();
    oss.str("");  //清空oss对象内所存储的流

    return s;
}

void fill(int i)
{
    switch(i)
    {
        case 1: {k1=v1; return;}
        case 2: {k2=v2; return;}
    }
}

void drop(int i)
{
    switch(i)
    {
        case 1: {k1=0; return;}
        case 2: {k2=0; return;}
    }
}

void pour(int i,int j)
{
    switch(i)
    {
        case 1:   //  v1 to v2
            {
                if(k1+k2<=v2)
                {
                    k2=k1+k2;
                    k1=0;
                }
                else
                {
                    k1=k1+k2-v2;
                    k2=v2;
                }
                return;
            }
        case 2:   //  v2 to v1
            {
                if(k1+k2<=v1)
                {
                    k1=k1+k2;
                    k2=0;
                }
                else
                {
                    k2=k1+k2-v1;
                    k1=v1;
                }
                return;
            }
    }
}

void BFS(void)
{
    int operation[1000]={0}; //当前步的操作: 1z0:清空z瓶子  2z0:装满z瓶子  3xy:从x瓶倒向y瓶

    map<string,bool>vist;
    vist["0,0"]=true;

    process queue[1000];  //状态队列
    int head,tail;
    queue[head=0].x=0;
    queue[tail=0].y=0;
    queue[tail++].step=0;

    string ts;  //temporary
    while(head<tail)
    {
        process p=queue[head];

        if(p.x==c || p.y==c)   //得到要求的剩余水量c
        {
            cout<<p.step<<endl;

            /*下标回溯,输出操作过程*/

            int ps=p.step;
            int* steps=new int[ps+1];  //从1到p.step顺序记录各步操作的下标,不使用steps[0]

            steps[ps--]=tail-1;
            while(ps)
            {
                steps[ps]=queue[ steps[ps+1] ].pos;
                ps--;
            }

            for(int i=1;i<=p.step;i++)
            {
                int temp=operation[ steps[i]-1 ];  //注意各个数组间的下标关系

                switch(temp/100)
                {
                    case 1:
                        {
                            cout<<"DROP("<<(temp/10)%10<<')'<<endl;
                            break;
                        }
                    case 2:
                        {
                            cout<<"FILL("<<(temp/10)%10<<')'<<endl;
                            break;
                        }
                    case 3:
                        {
                            cout<<"POUR("<<(temp/10)%10<<','<<temp%10<<')'<<endl;
                            break;
                        }
                }
            }

            delete steps;

            return;
        }

        /*装满v1*/

        k1=p.x;
        k2=p.y;
        fill(1);
        ts=combAB(k1,k2);
        if(!vist[ts])
        {
            vist[ts]=true;
            queue[tail].x=k1;
            queue[tail].y=k2;
            queue[tail].step=p.step+1;  //当前的操作步数
            queue[tail].pos=head;      //前一步操作在queue[]中的下标
            operation[tail++]=210;     //当前的操作
        }

        /*装满v2*/

        k1=p.x;
        k2=p.y;
        fill(2);
        ts=combAB(k1,k2);
        if(!vist[ts])
        {
            vist[ts]=true;
            queue[tail].x=k1;
            queue[tail].y=k2;
            queue[tail].step=p.step+1;
            queue[tail].pos=head;
            operation[tail++]=220;
        }

        /*清空v1*/

        k1=p.x;
        k2=p.y;
        drop(1);
        ts=combAB(k1,k2);
        if(!vist[ts])
        {
            vist[ts]=true;
            queue[tail].x=k1;
            queue[tail].y=k2;
            queue[tail].step=p.step+1;
            queue[tail].pos=head;
            operation[tail++]=110;
        }

        /*清空v2*/

        k1=p.x;
        k2=p.y;
        drop(2);
        ts=combAB(k1,k2);
        if(!vist[ts])
        {
            vist[ts]=true;
            queue[tail].x=k1;
            queue[tail].y=k2;
            queue[tail].step=p.step+1;
            queue[tail].pos=head;
            operation[tail++]=120;
        }

        /*v1倒向v2*/

        k1=p.x;
        k2=p.y;
        pour(1,2);
        ts=combAB(k1,k2);
        if(!vist[ts])
        {
            vist[ts]=true;
            queue[tail].x=k1;
            queue[tail].y=k2;
            queue[tail].step=p.step+1;
            queue[tail].pos=head;
            operation[tail++]=312;
        }

        /*v2倒向v1*/

        k1=p.x;
        k2=p.y;
        pour(2,1);
        ts=combAB(k1,k2);
        if(!vist[ts])
        {
            vist[ts]=true;
            queue[tail].x=k1;
            queue[tail].y=k2;
            queue[tail].step=p.step+1;
            queue[tail].pos=head;
            operation[tail++]=321;
        }

        head++;
    }

    cout<<"impossible"<<endl;
    return;
}

int main(void)
{
    while(cin>>v1>>v2>>c)
        BFS();
    return 0;
}

相关资料


文章作者: EXP
版权声明: 本博客所有文章除特別声明外,均采用 CC BY 4.0 许可协议。转载请注明来源 EXP !
 上一篇
POJ 1789 - Truck History POJ 1789 - Truck History
POJ 1789 - Truck History Time: 1000MS Memory: 65536K 难度: 初级 分类: 最小生成树算法 问题描述用一个7位的string代表一个编号,两个编号之间的distance代表这两个编号之
2011-02-19
下一篇 
POJ 1163 - The Triangle POJ 1163 - The Triangle
POJ 1163 - The Triangle Time: 1000MS Memory: 10000K 难度: 初级 分类: 动态规划 问题描述无。 解题思路和 POJ3176 的解释。 不骗人,确实是一模一样的代码 AC 源码//M
2011-02-16
  目录