1226 倒水问题
时间限制: 1 s
空间限制: 128000 KB
题目等级 : 黄金 Gold
题解
题目描述 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
先说明一下为什么我很少发广搜题目，因为蒟蒻po主的bfs不仅总写一大坨，而且基本都是有2,3个点死活过不去，所以才不敢露丑
———————————————我还是分割线—————————————
这道题在奥数题上经常看得到，不过对于oi来讲就是一道比较简单的bfs题目（难的我也不会做╮(╯_╰)╭），具体思路就是举出所有可能的操作（A→B，B→A，A→水缸，B→水缸，水缸→A，水缸→B）
代码：
#include<cstdio>#include<iostream>#include<cstring>using namespace std;int x,y,z;struct os{int a,b,ans;//ab指水壶状态，ans指步数}team[10001];bool flag[500][500];//判断当前状态是否已有，判重main(){memset(flag,false,sizeof(flag));scanf("%d%d%d",&x,&y,&z);int head=1;int tail=1;team[1].a=0;team[1].b=0;flag[0][0]=true;while (head<=tail){if (team[head].a>0&&team[head].b<y)//A→B{tail++;int aa=team[head].a;int bb=team[head].b;team[tail].a=aa-min(aa,y-bb); team[tail].b=bb+min(aa,y-bb);if (flag[team[tail].a][team[tail].b]==true) tail--;//若已有则出队else {flag[team[tail].a][team[tail].b]=true;team[tail].ans=team[head].ans+1;}if (team[tail].a==z||team[tail].b==z) {printf("%d",team[tail].ans);return 0;}}if (team[head].b>0&&team[head].a<x)//B→A{ tail++;int aa=team[head].a;int bb=team[head].b;team[tail].a=aa+min(bb,x-aa); team[tail].b=bb-min(bb,x-aa);if (flag[team[tail].a][team[tail].b]==true) tail--;else {flag[team[tail].a][team[tail].b]=true;team[tail].ans=team[head].ans+1;}if (team[tail].a==z||team[tail].b==z) {printf("%d",team[tail].ans);return 0;}}if (team[head].a>0)//A→水缸{tail++;team[tail].b=team[head].b;team[tail].a=0;if (flag[team[tail].a][team[tail].b]==true) tail--;else {flag[team[tail].a][team[tail].b]=true;team[tail].ans=team[head].ans+1;}if (team[tail].a==z||team[tail].b==z) {printf("%d",team[tail].ans);return 0;}} if (team[head].b>0)//B→水缸{tail++;team[tail].a=team[head].a;team[tail].b=0;if (flag[team[tail].a][team[tail].b]==true) tail--;else {flag[team[tail].a][team[tail].b]=true;team[tail].ans=team[head].ans+1;}if (team[tail].a==z||team[tail].b==z) {printf("%d",team[tail].ans);return 0;}}if (team[head].a<x)//水缸→A{tail++;team[tail].b=team[head].b;team[tail].a=x;if (flag[team[tail].a][team[tail].b]==true) tail--;else {flag[team[tail].a][team[tail].b]=true;team[tail].ans=team[head].ans+1;}if (team[tail].a==z||team[tail].b==z) {printf("%d",team[tail].ans);return 0;}} if (team[head].b<y)//水缸→B{tail++;team[tail].a=team[head].a;team[tail].b=y;if (flag[team[tail].a][team[tail].b]==true) tail--;else {flag[team[tail].a][team[tail].b]=true;team[tail].ans=team[head].ans+1;}if (team[tail].a==z||team[tail].b==z) {printf("%d",team[tail].ans);return 0;}}head++;}printf("impossible");}
注：本题比较难想的是A,B间的互相倒水操作，不过仔细思考就能获得解题思路
