正文
广度优先搜索 cdoevs 1226 倒水问题
小程序：扫一扫查出行【扫一扫了解最新限行尾号】
复制小程序
cdoevs 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
/*注意是两个瓶子在一起才能表示一种状态，考虑好两个瓶子之间倒水的八种情况：//向大壶倒满水
//向小壶倒满水
//大壶的水不要
//小壶的水不要
//大壶向小壶倒满水
//大壶向小壶倒水 ，倒不满
//小壶向大壶倒全部水，大壶没满
//小壶向大壶倒水，大壶满了
*/
#define N 120
#include<iostream>
using namespace std;
#include<cstdio>
bool visit[N][N];
#include<queue>
int x,y,z;
struct node{
int big,smal,sum;
};
int bfs(int &ans)
{
visit[][]=true;
queue<node>que;
que.push(node{,,});
while(!que.empty())
{
node now=que.front();
que.pop();
int a=now.big,b=now.smal,dep=now.sum;
if(a==z||b==z)
{
ans=dep;
return ;
}
if(!visit[x][b])
{
visit[x][b]=true;
que.push(node{x,b,dep+});
}
if(!visit[a][y])
{
visit[a][y]=true;
que.push(node{a,y,dep+});
}
if(!visit[][b])
{
visit[][b]=true;
que.push(node{,b,dep+});
}
if(!visit[a][])
{
visit[a][]=true;
que.push(node{a,,dep+});
}
if(a>=(y-b)&&!visit[a-(y-b)][y])
{
visit[a-(y-b)][y]=true;
que.push(node{a-(y-b),y,dep+});
}
if(a<y-b&&!visit[][a+b])
{
visit[][a+b]=true;
que.push(node{,a+b,dep+});
}if(b>=(x-a)&&!visit[x][b-(x-a)])
{
visit[x][b-(x-a)]=true;
que.push(node{x,b-(x-a),dep+});
}if(b<(x-a)&&!visit[a+b][])
{
visit[a+b][]=true;
que.push(node{a+b,,dep+});
}
}
}
int main()
{
int ans=;
scanf("%d%d%d",&x,&y,&z);
if(x<y) swap(x,y);
bfs(ans);
if(ans) printf("%d\n",ans);
else printf("impossible\n");
return ;
}
