想看更多的解题报告: http://iyenn.com/rec/1824570.html
                                     转载请注明出处：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 
#include 
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 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;
}