题目描述 Description
有两个无刻度标志的水壶，分别可装 x 升和 y 升 （ x,y 为整数且均不大于 100 ）的水。设另有一水 缸，可用来向水壶灌水或接从水壶中倒出的水， 两水壶间，水也可以相互倾倒。已知 x 升壶为空 壶， y 升壶为空壶。问如何通过倒水或灌水操作， 用最少步数能在x或y升的壶中量出 z （ z ≤ 100 ）升的水 来。
输入描述 Input Description
一行，三个数据，分别表示 x,y 和 z;
输出描述 Output Description
一行，输出最小步数 ,如果无法达到目标，则输出"impossible"
样例输入 Sample Input
3 22 1
样例输出 Sample Output
14
题解
bfs，一共有6种可能：
1、a桶倒空 2、b桶倒空
3、a桶倒满 4、b桶倒满
5、a桶倒入b桶
1）溢出
2）不溢出
6、b桶倒入a桶
1）溢出
2）不溢出
竟然把这里写错了。 
//5 x->y p = in; p.x = p.x - min(y-p.y,p.x); p.y = p.y + min(y-p.y,p.x); Q.push(p); //6 y->x p = in; p.x = p.x + min(x-p.x,p.y); p.y = p.y - min(x-p.x,p.y); Q.push(p);
#include<iostream> #include<queue> #include<cstdlib> #include<cstdio> #define N 1000 using namespace std; struct cup { int x,y,step; }first,now; int x,y,z; queue <cup> Q; bool f[N][N]; void extend(cup in) { if (f[in.x][in.y]) return; f[in.x][in.y] = 1; in.step++; //1 cup p = in; p.x = 0; Q.push(p); //2 p = in; p.y = 0; Q.push(p); //3 p = in; p.x = x; Q.push(p); //4 p = in; p.y = y; Q.push(p); //5 x->y p = in; p.x = in.x - min(y-in.y,in.x); p.y = in.y + min(y-in.y,in.x); Q.push(p); //6 y->x p = in; p.x = in.x + min(x-in.x,in.y); p.y = in.y - min(x-in.x,in.y); Q.push(p); } void bfs() { Q.push(first); while (!Q.empty()) { now = Q.front(); Q.pop(); if (now.x == z || now.y == z) { printf("%d",now.step); exit(0); } extend(now); } printf("impossible"); } int main() { scanf("%d%d%d",&x,&y,&z); first.step = first.x = first.y = 0; bfs(); }