• 如果您想对本站表示支持,请随手点击一下广告即可~
  • 本站致力于提供原创、优秀的技术文章~
  • 有任何疑问或建议 均可以在站点右侧栏处 通过各种方式联系站长哦~
  • POJ3414 – Pots

    ACM-POJ EXP 163阅读 0评论

    全解题报告索引目录 -> 【北大ACM – POJ试题分类


    题目大意

    给出了两个瓶子的容量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+k2 , k1=0 (有先后顺序)

       否则k1=k1+k2-v2 , k2=v2 (有先后顺序)

    Pour(2,1)亦同理

    转载请注明:EXP 技术分享博客 » POJ3414 – Pots

    喜欢 (0) 分享 (0)
    发表我的评论
    取消评论

    表情

    Hi,您需要填写昵称和邮箱!

    • 昵称 (必填)
    • 邮箱 (必填)
    • 网址