想看更多的解题报告: http://blog.csdn.net/wangjian8006/article/details/7870410
转载请注明出处：http://blog.csdn.net/wangjian8006
题目大意：
有二个水壶，对水壶有三种操作，1)FILL(i)，将i水壶的水填满，2)DROP(i)，将水壶i中的水全部倒掉，3)POUR(i,j)将水壶i中的水倒到水壶j中，若水壶 j 满了，则 i 剩下的就不倒了，问进行多少步操作，并且怎么操作，输出操作的步骤，两个水壶中的水可以达到C这个水量。如果不可能则输出impossible。初始时两个水壶是空的，没有水。
解题思路：
因为两个水壶A和B中的水量都不超过100，所以开个100*100的二维数组即可，map[i][j]表示第一个水壶中的水为i，第二个水壶中的水为j，BFS从0，0开始搜索，如果队列找完还没找完就找不到结果，而且BFS之后会生成一棵树，用parent表示这个节点的父亲节点，需要对这棵树进行操作，统计并从根节点开始输出。
代码：
#include <iostream>
#include <queue>
using namespace std;
#define MAXV 110
typedef struct Node{
int aa,bb,type,cout;
int i;
int pa,pb,ca,cb;
}VNode;
VNode map[MAXV][MAXV],v,temp;
bool dis[MAXV][MAXV];
void write(int first,int last){
int ft,lt;
printf("%d\n",map[first][last].cout);
map[first][last].ca=-1,map[first][last].cb=-1;
while(map[first][last].pa!=-1 && map[first][last].pb !=-1){
ft=first,lt=last;
v=map[map[first][last].pa][map[first][last].pb];
map[map[first][last].pa][map[first][last].pb].ca=first,map[map[first][last].pa][map[first][last].pb].cb=last;
first=v.aa,last=v.bb;
}
while(map[first][last].ca!=-1 && map[first][last].cb !=-1){
ft=first,lt=last;
switch(map[map[first][last].ca][map[first][last].cb].type){
case 1:printf("FILL(%d)\n",map[map[first][last].ca][map[first][last].cb].i);break;
case 2:printf("POUR(%d,%d)\n",map[map[first][last].ca][map[first][last].cb].i^3,map[map[first][last].ca][map[first][last].cb].i);break;
case 3:printf("DROP(%d)\n",map[map[first][last].ca][map[first][last].cb].i);break;
}
first=map[ft][lt].ca,last=map[ft][lt].cb;
}
}
int bfs(int a,int b,int c){
queue <VNode>q;
memset(dis,false,sizeof(dis));
memset(map,0,sizeof(map));
dis[0][0]=true;
map[0][0].pa=-1,map[0][0].pb=-1;
q.push(map[0][0]);
while(!q.empty()){
temp=v=q.front();
q.pop();
// printf("%d %d %d\n",v.aa,v.bb,v.cout);
v.aa=a;
if(!dis[v.aa][v.bb]){
dis[v.aa][v.bb]=true;
v.cout=temp.cout+1;
v.pa=temp.aa,v.pb=temp.bb;
v.type=1;
v.i=1;
map[v.aa][v.bb]=v;
if(v.aa==c || v.bb==c) {write(v.aa,v.bb);return 0;}
q.push(v);
}
v=temp;
v.bb=b;
if(!dis[v.aa][v.bb]){
dis[v.aa][v.bb]=true;
v.cout=temp.cout+1;
v.pa=temp.aa,v.pb=temp.bb;
v.type=1;
v.i=2;
map[v.aa][v.bb]=v;
if(v.aa==c || v.bb==c) {write(v.aa,v.bb);return 0;}
q.push(v);
}
v=temp;
v.aa=v.bb+v.aa;
if(v.aa>a) {
v.bb=v.aa-a;
v.aa=a;
}else v.bb=0;
if(!dis[v.aa][v.bb]){
dis[v.aa][v.bb]=true;
v.cout=temp.cout+1;
v.pa=temp.aa,v.pb=temp.bb;
v.type=2;
v.i=1;
map[v.aa][v.bb]=v;
if(v.aa==c || v.bb==c) {write(v.aa,v.bb);return 0;}
q.push(v);
}
v=temp;
v.bb=v.bb+v.aa;
if(v.bb>b) {
v.aa=v.bb-b;
v.bb=b;
}else v.aa=0;
if(!dis[v.aa][v.bb]){
dis[v.aa][v.bb]=true;
v.cout=temp.cout+1;
v.pa=temp.aa,v.pb=temp.bb;
v.type=2;
v.i=2;
map[v.aa][v.bb]=v;
if(v.aa==c || v.bb==c) {write(v.aa,v.bb);return 0;}
q.push(v);
}
v=temp;
v.aa=0;
if(!dis[v.aa][v.bb]){
dis[v.aa][v.bb]=true;
v.cout=temp.cout+1;
v.pa=temp.aa,v.pb=temp.bb;
v.type=3;
v.i=1;
map[v.aa][v.bb]=v;
if(v.aa==c || v.bb==c) {write(v.aa,v.bb);return 0;}
q.push(v);
}
v=temp;
v.bb=0;
if(!dis[v.aa][v.bb]){
dis[v.aa][v.bb]=true;
v.cout=temp.cout+1;
v.pa=temp.aa,v.pb=temp.bb;
v.type=3;
v.i=2;
map[v.aa][v.bb]=v;
if(v.aa==c || v.bb==c) {write(v.aa,v.bb);return 0;}
q.push(v);
}
}
// printf("a%d b%d %d\n",v.aa,v.bb,v.cout);
return -1;
}
int main(){
int a,b,c;
while(scanf("%d%d%d",&a,&b,&c)!=EOF){
a=bfs(a,b,c);
if(a==-1) printf("impossible\n");
}
return 0;
}
转载自原文链接, 如需删除请联系管理员。
原文链接：poj3414 - Pots，转载请注明来源！