H - Pots POJ - 3414
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 4
Sample Output
6
FILL(2)
POUR(2,1)
DROP(1)
POUR(2,1)
FILL(2)
POUR(2,1)
题意：有两个杯子，三种操作：1.把杯子倒满水 2.把杯子里的水倒掉 3.把一个杯子的水倒入另一个杯子。问能否得到目标的水的量。
思路：用bfs来模拟题意，via[5][7] = 1， 代表第一杯水有5 第二杯水有7 的情况出现过了。bfs的条件一共有六个，依次列出来就好。
此题难点在于如何去回溯bfs的路径。对于BFS的题而言这种要求是不太好解决的，我比较喜欢的一种方法是专门用一个ty类型的pre数组来存一下这一个点的上一个点是哪个。这里因为还需要存一下做了哪一个步骤才到了这一点,故对每种操作都编了号。pre[5][6].x=0，pre[5][6].y=6，pre[5][6].step=3 代表 第一杯水有5第二杯水有6的情况是由 第一杯水有0第二杯水有6的情况 通过操作3得到的。
代码：
#include <iostream>
#include <cstring>
#include <queue>
using namespace std;
typedef struct node {
int x,y;
int step;
} ty;
int n,i,j;
int now[3]; // 存放目前的情况
int ansx,ansy;
int lim[3]; // 存放容器大小
int tt[3]; // 暂存
int via[102][102]; // 判断此情况是否出现过
ty pre[102][102];
ty t,d;
int bfs()
{
t.x = now[0];
t.y = now[1];
t.step = 0;
via[t.x][t.y] = 1;
queue <ty> Q;
Q.push(t);
while ( !Q.empty() ) {
t = Q.front();
Q.pop();
now[0] = t.x;
now[1] = t.y;
if ( t.x==n || t.y==n ) {
ansx = t.x;
ansy = t.y;
return t.step ;
}
// 下面六大块代码 对应的是 六种情况
// 3 1
if ( now[0]>0 ) { // 这个判断不能少，不然如果第一杯里没有水，再让他倒也没法倒
tt[0] = now[0]; // 暂存一下，这次结束恢复初始状态
tt[1] = now[1];
int i = 0;
int j = 1;
if ( lim[j]>now[i]+now[j] ) {
now[j] += now[i];
now[i] = 0;
}
else {
now[i] -= lim[j]-now[j];
now[j] = lim[j];
}
d.x = now[0];
d.y = now[1];
d.step = t.step + 1;
if ( via[d.x][d.y]==0 ) {
via[d.x][d.y] = 1;
Q.push(d);
pre[d.x][d.y].x = t.x;
pre[d.x][d.y].y = t.y;
pre[d.x][d.y].step = 5;
}
now[0] = tt[0];
now[1] = tt[1];
}
// 3 2
if ( now[1]>0 ) {
tt[0] = now[0]; // 暂存一下，这次结束恢复初始状态
tt[1] = now[1];
i = 1;
j = 0;
if ( lim[j]>now[i]+now[j] ) {
now[j] += now[i];
now[i] = 0;
}
else {
now[i] -= lim[j]-now[j];
now[j] = lim[j];
}
d.x = now[0];
d.y = now[1];
d.step = t.step + 1;
if ( via[d.x][d.y]==0 ) {
via[d.x][d.y] = 1;
Q.push(d);
pre[d.x][d.y].x = t.x;
pre[d.x][d.y].y = t.y;
pre[d.x][d.y].step = 6;
}
now[0] = tt[0];
now[1] = tt[1];
}
// 1 1
tt[0] = now[0]; // 暂存一下，这次结束恢复初始状态
tt[1] = now[1];
d.x = lim[0];
d.y = now[1];
d.step = t.step + 1;
if ( via[d.x][d.y]==0 ) {
via[d.x][d.y] = 1;
Q.push(d);
pre[d.x][d.y].x = t.x;
pre[d.x][d.y].y = t.y;
pre[d.x][d.y].step = 1;
}
now[0] = tt[0];
now[1] = tt[1];
// 1 2
tt[0] = now[0]; // 暂存一下，这次结束恢复初始状态
tt[1] = now[1];
d.x = now[0];
d.y = lim[1];
d.step = t.step + 1;
if ( via[d.x][d.y]==0 ) {
via[d.x][d.y] = 1;
Q.push(d);
pre[d.x][d.y].x = t.x;
pre[d.x][d.y].y = t.y;
pre[d.x][d.y].step = 2;
}
now[0] = tt[0];
now[1] = tt[1];
// 2 1
tt[0] = now[0]; // 暂存一下，这次结束恢复初始状态
tt[1] = now[1];
d.x = 0;
d.y = now[1];
d.step = t.step + 1;
if ( via[d.x][d.y]==0 ) {
via[d.x][d.y] = 1;
Q.push(d);
pre[d.x][d.y].x = t.x;
pre[d.x][d.y].y = t.y;
pre[d.x][d.y].step = 3;
}
now[0] = tt[0];
now[1] = tt[1];
// 2 2
tt[0] = now[0]; // 暂存一下，这次结束恢复初始状态
tt[1] = now[1];
d.x = now[0];
d.y = 0;
d.step = t.step + 1;
if ( via[d.x][d.y]==0 ) {
via[d.x][d.y] = 1;
Q.push(d);
pre[d.x][d.y].x = t.x;
pre[d.x][d.y].y = t.y;
pre[d.x][d.y].step = 4;
}
now[0] = tt[0];
now[1] = tt[1];
}
return -1;
}
void pri( int x, int y ) // 对六种情况的编号
{
if ( x==0 && y==0 ) {
return ;
}
pri(pre[x][y].x,pre[x][y].y);
if ( pre[x][y].step==1 ) {
cout << "FILL(1)" << endl;
}
if ( pre[x][y].step==2 ) {
cout << "FILL(2)" << endl;
}
if ( pre[x][y].step==3 ) {
cout << "DROP(1)" << endl;
}
if ( pre[x][y].step==4 ) {
cout << "DROP(2)" << endl;
}
if ( pre[x][y].step==5 ) {
cout << "POUR(1,2)" << endl;
}
if ( pre[x][y].step==6 ) {
cout << "POUR(2,1)" << endl;
}
}
int main()
{
while ( cin >> lim[0]>>lim[1] >> n ) {
now[1] = now[0] = 0;
memset(via,0,sizeof(via));
int ans = bfs();
if ( ans==-1 ) {
cout << "impossible" << endl;
}
else {
cout << ans << endl;
pri(ansx,ansy);
}
}
return 0;
}