- POJ 3414 - Pots
- Time: 1000MS
- Memory: 65536K
- 难度: 初级
- 分类: BFS
0x00 POJ 原题
Description
You are given two pots, having the volume of A and B liters respectively. The following operations can be performed:
- 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).
Write a program to find the shortest possible sequence of these operations that will yield exactly C liters of water in one of the pots.
Input
On the first and only line are the numbers A, B, and C. These are all integers in the range from 1 to 100 and C≤max(A,B).
Output
The first line of the output must contain the length of the sequence of operations K. The following K lines must each describe one operation. If there are several sequences of minimal length, output any one of them. If the desired result can’t be achieved, the first and only line of the file must contain the word ‘impossible’.
Sample Input
3 5 4Sample Output
6
FILL(2)
POUR(2,1)
DROP(1)
POUR(2,1)
FILL(2)
POUR(2,1)Source
Northeastern Europe 2002, Western Subregion
0x10 题目概述
给出了两个瓶子的容量 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
0x20 解题思路
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=v1fill(2)相当于k2=v2drop(1)相当于k1=0drop(2)相当于k2=0对于
Pour(1,2)：若
k1+k2<=v2,则k2=k1+k2，k1=0（有先后顺序）否则
k1=k1+k2-v2，k2=v2（有先后顺序）Pour(2,1)亦同理
0x30 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;
}
