首页 > 代码库 > codevs1226 倒水问题
codevs1226 倒水问题
题目描述 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
思路：
普通广搜
代码：
#include<iostream>#include<cstdio>#include<string>#include<cstring>#include<algorithm>#define maxn 100000using namespace std;struct sta{ int x; int y; int step; int frm;};int mx,my,z,j[101][101],solved = 0;sta temp;void input(){ cin>>mx>>my>>z; temp.x = temp.y = temp.step = 0; temp.frm = -1;}sta expand(sta a,int sign){ if(sign == 0) a.x = 0; if(sign == 1) a.y = 0; if(sign == 2) a.x = mx; if(sign == 3) a.y = my; if(sign == 4){ int d; if(mx - a.x < a.y) d = mx - a.x; else d = a.y; a.y -= d; a.x += d; } if(sign == 5){ int d; if(my - a.y < a.x) d = my - a.y; else d = a.x; a.y += d; a.x -= d; } a.frm = sign; a.step++; if(j[a.x][a.y]) a.step = -1; j[a.x][a.y] = 1; return a;}void bfs(){ sta q[maxn]; int h = 0,t = 1; q[h] = temp; while(h != t){ if(q[h%maxn].x == z || q[h%maxn].y == z) { cout<<q[h%maxn].step<<endl; solved = 1; break; } for(int i = 0;i <= 5;i++){ if(i == 0 && (q[h%maxn].x == 0 ||q[h%maxn].frm == 2)) continue; if(i == 1 && (q[h%maxn].y == 0 ||q[h%maxn].frm == 3)) continue; if(i == 2 && (q[h%maxn].x == mx ||q[h%maxn].frm == 0)) continue; if(i == 3 && (q[h%maxn].y == my ||q[h%maxn].frm == 1)) continue; if(i == 4 && (q[h%maxn].y <= 0 || q[h%maxn].x >= mx || q[h%maxn].frm == 5)) continue; if(i == 5 && (q[h%maxn].x <= 0 || q[h%maxn].y >= my || q[h%maxn].frm == 4)) continue; temp = expand(q[h%maxn],i); if(temp.step != -1) { t++; q[t%maxn] = temp; } } h++; }}int main(){ input(); if(z > mx || z > my || !mx || !my || (mx == my && mx != z)){ cout<<"impossible"<<endl; return 0; } bfs(); if(!solved) cout<<"impossible"<<endl; return 0;}
codevs1226 倒水问题
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。