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间的互相倒水操作,不过仔细思考就能获得解题思路