week2 B - Pour Water

本文主要是介绍week2 B - Pour Water，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

问题描述:

倒水问题 “fill A” 表示倒满A杯，"empty A"表示倒空A杯，“pour A B” 表示把A的水倒到B杯并且把B杯倒满或A倒空，同理，“fill B” 表示倒满B杯，"empty B"表示倒空B杯，“pour B A” 表示把B的水倒到A杯并且把A杯倒满或B倒空。现有两个容量为A,B的杯子，无限水，如果要得到C容积的水，应该怎样操作？

Input：
输入包含多组数据。每组数据输入 A, B, C 数据范围 0 < A <= B 、C <= B <=1000 、A和B互质。

Output：
你的程序的输出将由一系列的指令组成。这些输出行将导致任何一个罐子正好包含C单位的水。每组数据的最后一行输出应该是“success”。输出行从第1列开始，不应该有空行或任何尾随空格。

解题思路：

深究原理，此题与迷宫路径相似，将状态用坐标表示，从起始状态到目的状态，中间经过一系列不同的状态，而由一个状态变为另一种状态，只有问题描述中的六种方法，故思考得，要记录每一状态的前一状态以及由何种方法转变。采用深度优先搜索（BFS)方法把从初始状态能够到达的不同状态入队列，直到达到目标状态或队列为空。

主要的数据结构：
① 方法标记二维数组sign——表示当前状态由前一状态经何种转变而来。0表示该状态未到达，1表示该点为初始状态，2、3、4、5、6、7分别对应各函数，即该状态由该方法转变而来，8对应目标状态。
② 标记当前状态的前一状态的pair<int,int>二维数组r——用坐标表示状态，记录该状态的前一状态。

步骤：（类似树的按层遍历）

访问初始点(sx,sy)，并将其标记为已访问过，sign置为1。
访问(sx,sy)的所有未被访问过可到达的状态点，并均标记为已访问过，即sign置为相应方法，前一坐标置为（sx，sy），将这些点加入到队列中。
再按照队列中的次序，访问每一个顶点（sx，sy）的所有未被访问过可到达的状态点，并做上相应标记，加入到队列中，依此类推。
直到到达终点（sign为8）或者初始状态能到达的所有状态都被访问了为止。

输出方法模块：
从初始点到目标点，每一个状态都记录了前一个状态以及相应的方法sign，故从目的状态往前遍历，借用栈结构保存sign，while循环，只要该点的sign不为1（没有到达初始状态），当前点的sign入栈，移向前一位置。最后，从栈中依次弹出sign值，输出对应方法即可。

实验代码：

#include<iostream>
#include<queue>
#include<utility>
#include<stack>
using namespace std;
int sign[1001][1001]={0};		int A,B,C; 		//全局变量 
typedef pair<int,int> pairtype;
pairtype r[1001][1001];		//存储前一位置 
void fillA(int& a,int& b)
{a=A;
//	return make_pair(a,b);
}
void fillB(int& a,int& b)
{b=B;
}
void emptyA(int& a,int& b)
{a=0;
}
void emptyB(int& a,int& b)
{b=0;
}
void  AtoB(int& a,int& b)		//将A倒空或者将B倒满，总之不溢出 
{if(a<=B-b){b+=a;a=0;		//A倒空 ，！!一定要注意顺序 }else {a=a-(B-b);		 b=B;		//B倒满 }
}
void BtoA(int& a,int& b)		//A倒满或者B倒空 
{if(b<=A-a)	{a+=b;		b=0;		//B倒空 }else{b=b-(A-a);	a=A;		//A倒满 } 
} 
pairtype pourtoC(int sa,int sb)		//初始状态，返回末状态 
{queue<pairtype> q;pairtype p1(sa,sb);sign[sa][sb]=1;		//!标记！表示该节点已经访问过 if(sa==C||sb==C)return p1; q.push(p1);		//初始状态队列while(!q.empty()) 		//调用六种函数 {p1=q.front();q.pop();int x1=p1.first,x2=p1.first,x3=p1.first,x4=p1.first,x5=p1.first,x6=p1.first;		//现有状态 int y1=p1.second,y2=p1.second,y3=p1.second,y4=p1.second,y5=p1.second,y6=p1.second;//该点可能到的几种状态 fillA(x1,y1);if(!sign[x1][y1])		//该点未到达{r[x1][y1]=p1;q.push(make_pair(x1,y1));sign[x1][y1]=2;		//表示由fillA方法而来	} else{if(sign[x1][y1]==8){r[x1][y1]=p1;sign[x1][y1]=2;return make_pair(x1,y1);}}emptyA(x2,y2);if(!sign[x2][y2])		//该点未到达{r[x2][y2]=p1;q.push(make_pair(x2,y2));sign[x2][y2]=3;		//表示由fillA方法而来	} else{if(sign[x2][y2]==8)		//到达终点 {r[x2][y2]=p1;sign[x2][y2]=3;return make_pair(x2,y2);}}AtoB(x3,y3);if(!sign[x3][y3])		//该点未到达{r[x3][y3]=p1;q.push(make_pair(x3,y3));sign[x3][y3]=4;		//表示由fillA方法而来	} else{if(sign[x3][y3]==8)		//到达终点 {r[x3][y3]=p1;sign[x3][y3]=4;return make_pair(x3,y3);}	}fillB(x4,y4);if(!sign[x4][y4])		//该点未到达{r[x4][y4]=p1;q.push(make_pair(x4,y4));sign[x4][y4]=5;		//表示由fillA方法而来	} else{if(sign[x4][y4]==8){r[x4][y4]=p1;sign[x4][y4]=5;return make_pair(x4,y4);}}emptyA(x5,y5);if(!sign[x5][y5])		//该点未到达{r[x5][y5]=p1;q.push(make_pair(x5,y5));sign[x5][y5]=6;		//表示由fillA方法而来	} else{if(sign[x5][y5]==8)		//到达终点 {r[x5][y5]=p1;sign[x5][y5]=6;return make_pair(x5,y5);}}BtoA(x6,y6);if(!sign[x6][y6])		//该点未到达{r[x6][y6]=p1;q.push(make_pair(x6,y6));sign[x6][y6]=7;		//表示由fillA方法而来	} else{if(sign[x6][y6]==8)		//到达终点 {r[x6][y6]=p1;sign[x6][y6]=7;return make_pair(x6,y6);}}}return  make_pair(-1,-1); 
} void output(int tx,int ty)		//从(tx,ty)状态返回 
{stack<int> s;		//存储中间函数的栈，因为要倒着输出 int zt=sign[tx][ty];pairtype p(tx,ty);int x,y;while(zt!=1)		//没有回到初始点 {s.push(zt);x=p.first;y=p.second;p=r[x][y];		//找到前一位置 zt=sign[p.first][p.second];		//前一位置的状态 }while(!s.empty()){int zt=s.top();s.pop();switch(zt){case 2:{cout<<"fill A"<<endl;break;}case 3:{cout<<"empty A"<<endl;break;}case 4:{cout<<"pour A B"<<endl;break;}case 5:{cout<<"fill B"<<endl;break;}case 6:{cout<<"empty B"<<endl;break;}case 7:{cout<<"pour B A"<<endl;break;}}}cout<<"success"<<endl;
}
int main(void)
{while(cin>>A>>B>>C){//数组初始化 for(int i=0;i<=A;i++)for(int j=0;j<=B;j++){if(i==C||j==C)sign[i][j]=8;else sign[i][j]=0;r[i][j].first=-1;r[i][j].second=-1;}pairtype p=pourtoC(0,0);if(p.first!=-1)output(p.first,p.second);}return 0;
}