题目描述：
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 jis 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) 这个题目对我而言，我现在的编码搜索水平简直是一个挑战，但是没想到一遍过了(暗自窃喜)，真的提升太大了，下面分享一下思路。
第一步：读懂题意，题目要求A杯子与B杯子任何一个杯子中的水的体积到达C就可以，给出了三种操作 实际上是八种情况，根据BFS的性质，我们可以用一个二维数组标记，A杯子B杯子的状态，开到a[300][300]就够了，题目最多100。
第二步：根据BFS的顺序，把每一步对应的状态继续放入BFS中，并做一下标记，因为后来再有到这个状态需要改动的次数绝对比现在多。
第三步：标记完之后，把一个状态考虑清楚，比如说 从A 向 B 倒水，需要判断 B会不会满，满的话A中绝对有剩余。
第四步：记录一下路径，在这里我记录的路径是建立一个结构体，利用链式前向星的思想，储存上一个数组所在的标号，和当前数组所在的标号，具体还需要看代码。
第五步：还是判断记录路径中，每一步都干了些什么？那可以定义一个flag如果执行 填满 操作 flag=1,倾倒操作 flag=2，清空操作 flag=3。然后 注意 倾倒操作的顺序，还有 填满，清空操作的对象。用st->en表示由st 倒入 en。
剩下全是细节问题，具体也解释不太清楚细节，附一下代码，码量比较大，一次过也算万幸了：
#include <queue>
#include <cstdio>
#include <stdlib.h>
#include <string.h>
#include <math.h>
#include <iostream>
#include <stack>
#include <algorithm>
#include <vector>
#define MIN(x,y) ((x)<(y)?(x) : (y))
#define MAX(x,y) ((x)>(y)?(x) : (y))
using namespace std;
typedef long long ll;
const int mod=10007;
const int INF=0x3f3f3f3f;
const int maxn=1e6+5;
struct node{
int staa,stab;
int flag;
int st,en;
int pri,cnt1;//s代表填充值和drop值，也代表A->B的A
}Q[10005];
int a,b,c;
int dis[1000][1000];//代表 a为x，b为y时的最小步数
bool vis[1000][1000];//标记访问
int cnt=0;
int bfs()
{
queue<node>q;
memset(vis,false,sizeof(vis));
q.push(Q[1]);
dis[0][0]=0;
vis[0][0]=true;
while(!q.empty())
{
node pre=q.front();q.pop();
// printf("%d %d \n",pre.staa,pre.stab);
if(pre.staa==c||pre.stab==c) return pre.cnt1;
if(pre.stab!=0)// 将b倒入a,那a绝对不可能为0
{
node now;
if(pre.staa+pre.stab>=a)//用数学验证一下。
{
now.stab=pre.staa+pre.stab-a;
now.staa=a;
if(vis[now.staa][now.stab]==false)
{
now.flag=2;now.st=2;now.en=1;
now.pri=pre.cnt1;
Q[++cnt]=now;
Q[cnt].cnt1=cnt;
q.push(Q[cnt]);//这里是因为刚开始没看到要记录路径，后来又加的其实完全可以直接Q数组
vis[now.staa][now.stab]=true;//标记访问
dis[now.staa][now.stab]=dis[pre.staa][pre.stab]+1;//到这个状态的次数+1
}
}
else
{
now.stab=0;
now.staa=pre.staa+pre.stab;
if(vis[now.staa][now.stab]==false)
{
now.flag=2;now.st=2;now.en=1;
now.pri=pre.cnt1;
Q[++cnt]=now;
Q[cnt].cnt1=cnt;
q.push(Q[cnt]);
vis[now.staa][now.stab]=true;
dis[now.staa][now.stab]=dis[pre.staa][pre.stab]+1;
}
}
}
if(pre.staa!=0)
{
node now;
if(pre.staa+pre.stab>=b)
{
now.staa=pre.staa+pre.stab-b;
now.stab=b;
if(vis[now.staa][now.stab]==false)
{
now.flag=2;now.st=1;now.en=2;
now.pri=pre.cnt1;
Q[++cnt]=now;
Q[cnt].cnt1=cnt;
q.push(Q[cnt]);
vis[now.staa][now.stab]=true;
dis[now.staa][now.stab]=dis[pre.staa][pre.stab]+1;
}
}
else
{
now.stab=pre.staa+pre.stab;
now.staa=0;
if(vis[now.staa][now.stab]==false)
{
now.flag=2;now.st=1;now.en=2;
now.pri=pre.cnt1;
Q[++cnt]=now;
Q[cnt].cnt1=cnt;
q.push(Q[cnt]);
vis[now.staa][now.stab]=true;
dis[now.staa][now.stab]=dis[pre.staa][pre.stab]+1;
}
}
}
if(pre.staa!=a) //填满操作
{
node now;
now.staa=a;now.stab=pre.stab;
now.flag=1;now.st=1;
if(vis[now.staa][now.stab]==false)
{
vis[now.staa][now.stab]=true;
dis[now.staa][now.stab]=dis[pre.staa][pre.stab]+1;
now.pri=pre.cnt1;
Q[++cnt]=now;
Q[cnt].cnt1=cnt;
q.push(Q[cnt]);
}
}
if(pre.stab!=b) 填满操作
{
node now;
now.staa=pre.staa;now.stab=b;
now.flag=1;now.st=2;
if(vis[now.staa][now.stab]==false)
{
vis[now.staa][now.stab]=true;
dis[now.staa][now.stab]=dis[pre.staa][pre.stab]+1;
now.pri=pre.cnt1;
Q[++cnt]=now;
Q[cnt].cnt1=cnt;
q.push(Q[cnt]);
}
}
if(pre.staa!=0)//清空操作
{
node now;
now.staa=0;now.stab=pre.stab;
now.flag=3;now.st=1;
if(vis[now.staa][now.stab]==false)
{
vis[now.staa][now.stab]=true;
dis[now.staa][now.stab]=dis[pre.staa][pre.stab]+1;
now.pri=pre.cnt1;
Q[++cnt]=now;
Q[cnt].cnt1=cnt;
q.push(Q[cnt]);
}
}
if(pre.stab!=0)
{
node now;
now.stab=0;now.staa=pre.staa;
now.flag=3;now.st=2;
if(vis[now.staa][now.stab]==false)
{
vis[now.staa][now.stab]=true;
dis[now.staa][now.stab]=dis[pre.staa][pre.stab]+1;
now.pri=pre.cnt1;
Q[++cnt]=now;
Q[cnt].cnt1=cnt;
q.push(Q[cnt]);
}
}
}
return -1;//不要忘记 没有 的可能
}
void solved(int n)//用回溯法输出路径，记录最后一个为flag=-1，之后进行回溯
{
if(Q[n].flag==-1)
return;
else
{
solved(Q[n].pri);
if(Q[n].flag==1)
printf("FILL(%d)\n",Q[n].st);
else if(Q[n].flag==2)
printf("POUR(%d,%d)\n",Q[n].st,Q[n].en);
else if(Q[n].flag==3)
printf("DROP(%d)\n",Q[n].st);
}
}
int main()
{
while(~scanf("%d%d%d",&a,&b,&c))
{
cnt=0;
Q[++cnt].staa=0;Q[cnt].stab=0;
Q[cnt].flag=-1;Q[cnt].cnt1=1;
Q[cnt].pri=1;
int ans=bfs();
if(ans==-1) printf("impossible\n");
else
{
printf("%d\n",dis[Q[ans].staa][Q[ans].stab]);
solved(ans);
}
}
return 0;
} 祝大家一次AC，加油！
京公网安备 11010502036488号