回复 11楼 beyondyf
#include <stdio.h>
typedef struct Node{
int have_v[3];//状态的水量
int size_v[3];//对应瓶子的容量
int step;
int father;
}Node;
typedef struct dumpWaterTable{
int v[2];
}dumpWaterTable;//倒水表单元结构
dumpWaterTable table_dump_methods[6] = {{0,1},{0,2},{1,0},{1,2},{2,0},{2,1}};//倒水方法表
Node queue[100000];//存储各个状态量的队列
int front,rear;
void Init(int &a, int &b, int &c, Node & root,bool flag);//初始化搜索根结点
bool bfs(Node & root,int x);//宽度优先搜素
void Print_L(int index,int now);//按照找到的结点，递归打印倒水过程
bool isequal(Node &a,int &b);//判断是否出现合法的且有水杯的水等于b
bool isvalid(int i,Node v,Node & dumped);//判断倒水表中第i中方法是否合适
int min(int a, int b);//返回最小值
//void testout(Node & v);
int a,b,c;
int main(){
int x;
while(scanf("%d%d%d%d",&a,&b,&c,&x)!=EOF){//输入各个瓶子的容量,已经目标容量的为x
Node root;//根结点
Init(a,b,c,root,true);//根结点初始化
front = rear = 0;
bfs(root,x);//开始搜索
}
return 0;
}
void Print_L(int index,int now){//递归打印
int key = queue[index].step;
int fa = queue[index].father;
if(key != 0){
Print_L(fa,now + 1);
}
if(index == 0)
printf("至少需要%d步\n",now);
printf("(%d,%d,%d)\n",queue[key].have_v[0],queue[key].have_v[1],queue[key].have_v[2]);
}
void Init(int &a, int &b, int &c, Node & root,bool flag){
if(flag){
root.have_v[0] = a;
root.have_v[1] = 0;
root.have_v[2] = 0;
root.size_v[0] = a;
root.size_v[1] = b;
root.size_v[2] = c;
root.step = root.father= 0;
}
else{
root.size_v[0] = a;
root.size_v[1] = b;
root.size_v[2] = c;
}
}
bool bfs(Node & root,int x){
queue[rear++] = root;//根结点入队列
int step = 0;
bool Have_Find = false;//没发现目标结点
while(front < rear){
Node v = queue[front++];//出队列
if(isequal(v,x)){
Have_Find = true;
break;
}
for(int i = 0; i < 6; i++){//尝试各种倒水法,合法就拓展入队列
Node dumped;
Init(a,b,c,dumped,false);
if(isvalid(i,v,dumped)){
dumped.step = ++step;
dumped.father = v.step;
queue[rear++] = dumped;
}
}
}
if(Have_Find){
Print_L(front - 1,0);
}
else{
printf("亲,无解\n");
}
}
bool isequal(Node &a,int & b){
for(int i =0; i < 3 ;i++){
if(a.have_v[i] == b)
return true;
}
return false;
}
bool isvalid(int i,Node v,Node & dumped){
dumpWaterTable m = table_dump_methods[i];//取得倒水表第i中方式,m为方式变量,m.v[0]倒到m.v[1]
if(v.have_v[m.v[0]] != 0 && v.have_v[m.v[1]] != v.size_v[m.v[1]]){//可倒水
int d = min(v.have_v[m.v[0]],v.size_v[m.v[1]] - v.have_v[m.v[1]]);
dumped.have_v[m.v[0]] = v.have_v[m.v[0]] - d;
dumped.have_v[m.v[1]] = v.have_v[m.v[1]] + d;
int j;
for(j = 0; j < 3; j++){//搜索没有参与倒水的瓶子
if(j != m.v[0] && j != m.v[1])
break;
}
dumped.have_v[j] = v.have_v[j];//保存没参与倒水的瓶子
return true;//返回合法该方法合法,并且已经执行。
}
return false;
}
int min(int a,int b){
return a < b ? a : b;
}
//void testout(Node &v){
// printf("testing(%d,%d,%d)\n",v.have_v[0],v.have_v[1],v.have_v[2]);
//}
程序代码：