题目描述 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
比小白上的倒水问题弱多了……宽搜+if练习题
代码：
using namespace std;int x,y,target;struct state{int x,y,step;}f;queue<state> q;bool vis[233][233];int bfs(){q.push(f);vis[f.x][f.y]=1;while(q.size()){f=q.front(); q.pop();if(f.x==target||f.y==target) return f.step;if(f.x<x&&vis[x][f.y]==0) //x倒满{q.push((state){x,f.y,f.step+1});vis[x][f.y]=1;}if(f.x&&vis[0][f.y]==0) //x倒空{q.push((state){0,f.y,f.step+1});vis[0][f.y]=1;}if(f.y<y&&vis[f.x][y]==0) //y倒满{q.push((state){f.x,y,f.step+1});vis[f.x][y]=1;}if(f.y&&vis[f.x][0]==0) //y倒空{q.push((state){f.x,0,f.step+1});vis[f.x][0]=1;}if(f.x>=y-f.y&&vis[f.x-(y-f.y)][y]==0)//x->y{q.push((state){f.x-(y-f.y),y,f.step+1});vis[f.x-(y-f.y)][y]=1;}if(f.x<y-f.y&&vis[0][f.x+f.y]==0)//x->y{q.push((state){0,f.x+f.y,f.step+1});vis[0][f.x+f.y]=1;}if(f.y>=x-f.x&&vis[x][f.y-(x-f.x)]==0)//y->x{q.push((state){x,f.y-(x-f.x),f.step+1});vis[x][f.y-(x-f.x)]=1;}if(f.y<x-f.x&&vis[f.x+f.y][0]==0)//y->x{q.push((state){f.x+f.y,0,f.step+1});vis[f.x+f.y][0]=1;}}return -1;}int main(){scanf(“%d%d%d”,&x,&y,&target);int ans=bfs();if(ans!=-1) printf(“%d”,ans);else printf(“impossible”);return 0;}
当你能梦的时候就不要放弃梦
