数据:
Sample Input:
2 7 5
2 7 4
Sample Output:
fill B
pour B A
success
fill A
pour A B
fill A
pour A B
success
#include <iostream>
#include <queue>
#include <stack>
using namespace std;
int AtoBb(int B, int a, int b){
if(a<=B-b) return b+a;
return B;
}
int AtoBa(int B, int a, int b){
if(a<=B-b) return 0;
return a+b-B;
}
int BtoAa(int A, int a, int b){
if(b<=A-a) return a+b;
return A;
}
int BtoAb(int A, int a, int b){
if(b<=A-a) return 0;
return a+b-A;
}
void bfs(int A, int B, int C){
queue<int> P;
queue<int> Q;
stack<int> Lu;
int X[A+1][B+1] ;
int Y[A+1][B+1];
int M[A+1][B+1];
for(int i=0; i<A+1; i++){
for(int j=0; j<B+1; j++){
M[i][j]=0;
}
}
M[0][0]=-1;
P.push(0);
Q.push(0);
int a=0,b=0;
while(a!=C || b!=C || !P.empty()){
int a1=P.front();
P.pop();
int b1=Q.front();
Q.pop();
int i=1;
for(; i<=6; i++){
if(i==1){
a=A;
b=b1;
}else if(i==2){
a=a1;
b=B;
}else if(i==3){
a=AtoBa(B,a1,b1);
b=AtoBb(B,a1,b1);
}else if(i==4){
a=BtoAa(A,a1,b1);
b=BtoAb(A,a1,b1);
}else if(i==5){
a=0;
b=b1;
}else if(i==6){
a=a1;
b=0;
}
if(M[a][b]==0){
M[a][b]=i;
P.push(a);
Q.push(b);
X[a][b]=a1;
Y[a][b]=b1;
}
if(a==C || b==C) break;
}
if(a==C || b==C) break;
}
Lu.push(a);
Lu.push(b);
while(a!=0 || b!=0){
int m=X[a][b];
int n=Y[a][b];
a=m;
b=n;
Lu.push(a);
Lu.push(b);
}
Lu.pop();
Lu.pop();
while(!Lu.empty()){
int n=Lu.top();
Lu.pop();
int m=Lu.top();
Lu.pop();
if(M[m][n]==1){
cout<<"fill A"<<endl;
}else if(M[m][n]==2){
cout<<"fill B"<<endl;
}else if(M[m][n]==3){
cout<<"pour A B"<<endl;
}else if(M[m][n]==4){
cout<<"pour B A"<<endl;
}else if(M[m][n]==5){
cout<<"empty A"<<endl;
}else if(M[m][n]==6){
cout<<"empty B"<<endl;
}
}
cout<<"success"<<endl;
}
int main(){
int A,B,C;
ios::sync_with_stdio(false);
while(cin>>A>>B>>C){
bfs(A,B,C);
}
return 0;
}
思路:和迷宫问题一样,都是属于用bfs进行路径搜索的题目,不过倒水问题的下一步移动的方向距离是隐藏的,并不是确定的,故需要处理一下这个问题。其他基本和迷宫问题一样,不断搜索点,然后保存前一个点的坐标,最后到达终点后,从终点将路径反向输出即可。
本文内容由网友自发贡献,版权归原作者所有,本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容,请联系:hwhale#tublm.com(使用前将#替换为@)