codevs 1226 倒水问题

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

枚举八种可能情况进行bfs

注意要判重

 1 #include<cstdio>
 2 #include<iostream>
 3 #include<queue>
 4 using namespace std;
 5 int n;int m,z;
 6 
 7 struct miku{
 8     int x;int y,step;
 9 }cur,nxt;
10 
11 queue<miku>que;
12 
13 bool can(int x,int y)
14 {
15     if(x>=0&&y>=0&&x<=n&&y<=m)
16      return 1;
17      return 0;
18 }
19 
20 int ans;
21 bool vis[1000][1000];
22 void bfs(int x,int y)
23 {
24     cur.x=x;cur.y=y;cur.step=0;
25     que.push(cur);
26     while(!que.empty())
27     {
28         cur=que.front();
29         que.pop();
30         for(int i=1;i<=8;i++)
31         {
32             int next_x,next_y;
33             if(i==1)next_x=0,next_y=cur.y+cur.x;//x->y倒空 
34             else if(i==2)next_x=cur.x+cur.y,next_y=0;//y->x倒空 
35             else if(i==3)next_x=n,next_y=cur.y;//倒满x 
36             else if(i==4)next_x=cur.x,next_y=m;//倒满y 
37             else if(i==5)next_x=0,next_y=cur.y;//清空x 
38             else if(i==6)next_x=cur.x,next_y=0;//清空y 
39             else if(i==7)next_x=n,next_y=cur.y-(n-cur.x);//y->x不倒空 
40             else if(i==8)next_x=cur.x-(m-cur.y),next_y=m;//x->y不倒空 
41             if(can(next_x,next_y))
42             if(next_x==z||next_y==z)
43             {
44                 ans=cur.step+1;
45                 return ;
46             }
47             if(can(next_x,next_y)&&!vis[next_x][next_y])
48             {
49                 vis[next_x][next_y]=1;
50                 nxt.x=next_x;
51                 nxt.y=next_y;
52                 nxt.step=cur.step+1;
53                 que.push(nxt);
54             }
55         }
56     }
57 }
58 int main()
59 {
60     scanf("%d%d%d",&n,&m,&z);
61     bfs(0,0);
62     if(ans!=0)
63     printf("%d",ans);
64     else printf("impossible");
65     return 0;
66 }