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
枚举八种可能情况进行bfs
注意要判重
#include<cstdio>
#include<iostream>
#include<queue>
using namespace std;
int n;int m,z; struct miku{
int x;int y,step;
}cur,nxt; queue<miku>que; bool can(int x,int y)
{
if(x>=&&y>=&&x<=n&&y<=m)
return ;
return ;
} int ans;
bool vis[][];
void bfs(int x,int y)
{
cur.x=x;cur.y=y;cur.step=;
que.push(cur);
while(!que.empty())
{
cur=que.front();
que.pop();
for(int i=;i<=;i++)
{
int next_x,next_y;
if(i==)next_x=,next_y=cur.y+cur.x;//x->y倒空
else if(i==)next_x=cur.x+cur.y,next_y=;//y->x倒空
else if(i==)next_x=n,next_y=cur.y;//倒满x
else if(i==)next_x=cur.x,next_y=m;//倒满y
else if(i==)next_x=,next_y=cur.y;//清空x
else if(i==)next_x=cur.x,next_y=;//清空y
else if(i==)next_x=n,next_y=cur.y-(n-cur.x);//y->x不倒空
else if(i==)next_x=cur.x-(m-cur.y),next_y=m;//x->y不倒空
if(can(next_x,next_y))
if(next_x==z||next_y==z)
{
ans=cur.step+;
return ;
}
if(can(next_x,next_y)&&!vis[next_x][next_y])
{
vis[next_x][next_y]=;
nxt.x=next_x;
nxt.y=next_y;
nxt.step=cur.step+;
que.push(nxt);
}
}
}
}
int main()
{
scanf("%d%d%d",&n,&m,&z);
bfs(,);
if(ans!=)
printf("%d",ans);
else printf("impossible");
return ;
}