yzoi1777倒水问题的详细解法
Description - 问题描述
输入只有一行，即4个整数：
xMax yMax zMax n
其中100>xMax>yMax>zMax，n<100
Output - 输出数据
对于每个测试数据，输出其倒水步骤，如果步骤只有一步，step不加s请参考Sample Output，无解的话输出“No Solution”
算法分析
首先，我们需要考虑倒出者和接收者的可能分别为x->y,x->z（前提是x>0);y->x,y->z（前提是y>0);z->x,z->y（前提是z>0)共6种可能，接下来我们便对其进行详细分析。
①x->y时
前提：if（x>0),接着，我们要考虑的就是当将x中所有水倒入y中，是否已经超过了y的容量，代码如下
if(x>)
{
if(x+y>ymax)
{
x=x-(ymax-y);//将x中所有水倒入y中时已超出y的最大容量
y=ymax;
}
else
{
y=x+y;//将x中所有水倒入y中后未超过其最大容量
x=;//即x中的水全部倒入y中，x变为空
}
}
②x->z时
前提：if(x>0)这时，我们可以将x->z的过程类比成x->y的过程，其实际上的过程是一样的，代码如下：
if(x>)
{
if(x+z>zmax)
{
x=x-(zmax-z);//z容器倒满
z=zmax;
}
else
{
z=z+x;//x倒空
x=;
}
}
③y->x时
前提：if(y>0),这是，我们还要不要像以前那样考虑y会不会倒空，已及x会不会倒满呢？其答案是否定的，为什么呢？你可以设想：在整个装置（包括x，y以及z）中，其总水量之和为xmax。故不管y如何倒都不会使x>xmax，代码如下：
if(y>)
{
x=x+y;//y倒空
y=;
}
④y->z时,同x->y
⑤z->x时,同y->x
⑥z->y,这里也是同y->x吗？其实不然，当y->x时，无论如何都不会使x>xmax。但当z->y时却有可能使y>ymax，很多人都跳入了这个坑里，导致最终程序不能ac。经过仔细思考之后，其实可以知道这是和x->y一样的。代码如下：
if(z>)
{
if(z+y>ymax)
{
z=z-(ymax-y);
y=ymax;
}
else
{
y=y+z;
z=;
}
}
在对倒水的过程进行详细分析之后，最重要的便是算法的构造。仔细分析可以知道，这道题是要求我们分析倒水的每种情况，然后找出最优解。毫无疑问，这便是bfs的思路。可能有些人不了解或对bfs接触较少，这里给上百度对其的解释以助理解：
BFS一般指宽度优先搜索，宽度优先搜索算法（又称广度优先搜索）是最简便的图的搜索算法之一，这一算法也是很多重要的图的算法的原型。Dijkstra单源最短路径算法和Prim最小生成树算法都采用了和宽度优先搜索类似的思想。其别名又叫BFS，属于一种盲目搜寻法，目的是系统地展开并检查图中的所有节点，以找寻结果。换句话说，它并不考虑结果的可能位置，彻底地搜索整张图，直到找到结果为止。而在这个问题中，我们使用队列（queue）来实现之。
首先，假设我们已经定义了一个队列q，如下所示
struct node
{
int qx,qy,qz;
int pre;
} q[maxn];
其中qx，qy，qz表示当前各个装置中水的含量，而对于pre，相信大多数人都会纳闷：这是用来干什么的呢？其实，当你仔细阅读题目便可知道，它不仅要求输出最少次数，还得打印出每倒一次水的步骤，这里的pre便是用以存储当前状态所对应的上一个状态，到最后输出时，只需沿着pre进行输出即可。
void push()
{
bool can_push=true;
for(int i=;i<=rear;i++)
{
if(q[i].qx==x&&q[i].qy==y&&q[i].qz==z)
{
can_push=false;
return;
}
}
if(can_push)
{
rear++;
q[rear].qx=x;
q[rear].qy=y;
q[rear].qz=z;
q[rear].pre=front;
}
}
同时，在倒水时如果先前已经出现了与当前状态一致的状态，那还要不要继续倒呢？显然，答案是否定的，而这里的bool型变量can_push正是帮助完成了这一点.
在倒完水后，我们还需判断是否达到了目标状态，如果达到了就跳出循环，然后输出过程，代码如下：
void is_target()
{
if(q[rear].qx==n||q[rear].qy==n||q[rear].qz==n)
flag=true;
else
flag=false;
}
细心的人可能会发现：在模拟倒水过程时的x，y，z三个变量是哪来的呢？以是，我们还得写个取队首元素的函数，代码如下;
void initial()
{
x=q[front].qx;
y=q[front].qy;
z=q[front].qz; }
最后，我们再将刚刚模拟过的6种情况写下，再加一个while循环便可完成任务。接下来还有一点值得思考：这里的while循环的条件是什么。还记得题目中给出的“No Solution”吗。是的，在最后跳出循环后我们还得加一条is_target()(其实在跳出循环之前已经执行了一次is_target()，故只需判断flag即可)以判断是否有解。经过这样的分析后，while执行的条件便是队列是否为空is_empty()。倒水总过程的代码如下：
void pour()
{
while(front <= rear)
{
initial();
//x->y
if(x>)
{
if(x+y>ymax)
{
x=x-(ymax-y);
y=ymax;
}
else
{
y=x+y;
x=;
}
}
push();
is_target();
if(flag)
break;
//x->z
initial();
if(x>)
{
if(x+z>zmax)
{
x=x-(zmax-z);
z=zmax;
}
else
{
z=z+x;
x=;
}
}
push();
is_target();
if(flag)
break;
//y->x
initial();
if(y>)
{
x=x+y;
y=;
}
push();
is_target();
if(flag)
break;
//y->z
initial();
if(y>)
{
if(y+z>zmax)
{
y=y-(zmax-z);
z=zmax;
}
else
{
z=y+z;
y=;
}
}
push();
is_target();
if(flag)
break;
//z->x
initial();
if(z>)
{
x=x+z;
z=;
}
push();
is_target();
if(flag)
break;
//z->y
initial();
if(z>)
{
if(z+y>ymax)
{
z=z-(ymax-y);
y=ymax;
}
else
{
y=y+z;
z=;
}
}
push();
is_target();
if(flag)
break;
front++;
}
}
还有一点要补充的就是这题也可以用STL里的queue来做，这样便可省去自己写队列的麻烦。
最后，给上OJ上ac的代码，仅供参考：
/*
Name: lwq
Copyright:
Author:
Date: 07/12/14 00:57
Description: 1777
*/ #include<iostream>
using namespace std;
const int maxn=+;
int front,rear;
int xmax,ymax,zmax;
int n;
int x,y,z;
int step=;
int k=;
bool flag=false;
struct node
{
int qx,qy,qz;
int pre;
} q[maxn];
struct node_data
{
int x,y,z;
}data[maxn];
void is_target()
{
if(q[rear].qx==n||q[rear].qy==n||q[rear].qz==n)
flag=true;
else
flag=false;
}
void initial()
{
x=q[front].qx;
y=q[front].qy;
z=q[front].qz; }
void push()
{
bool can_push=true;
for(int i=;i<=rear;i++)
{
if(q[i].qx==x&&q[i].qy==y&&q[i].qz==z)
{
can_push=false;
return;
}
}
if(can_push)
{
rear++;
q[rear].qx=x;
q[rear].qy=y;
q[rear].qz=z;
q[rear].pre=front;
}
}
void pour()
{
while(front <= rear)
{
initial();
//x->y
if(x>)
{
if(x+y>ymax)
{
x=x-(ymax-y);
y=ymax;
}
else
{
y=x+y;
x=;
}
}
push();
is_target();
if(flag)
break;
//x->z
initial();
if(x>)
{
if(x+z>zmax)
{
x=x-(zmax-z);
z=zmax;
}
else
{
z=z+x;
x=;
}
}
push();
is_target();
if(flag)
break;
//y->x
initial();
if(y>)
{
x=x+y;
y=;
}
push();
is_target();
if(flag)
break;
//y->z
initial();
if(y>)
{
if(y+z>zmax)
{
y=y-(zmax-z);
z=zmax;
}
else
{
z=y+z;
y=;
}
}
push();
is_target();
if(flag)
break;
//z->x
initial();
if(z>)
{
x=x+z;
z=;
}
push();
is_target();
if(flag)
break;
//z->y
initial();
if(z>)
{
if(z+y>ymax)
{
z=z-(ymax-y);
y=ymax;
}
else
{
y=y+z;
z=;
}
}
push();
is_target();
if(flag)
break;
front++;
}
}
int main()
{
front=,rear=;
cin>>xmax>>ymax>>zmax;
cin>>n;
q[front].qx=xmax;
q[front].qy=;
q[front].qz=;
pour(); if(flag)
{ while(q[rear].pre>)
{
k++;
data[k].x=q[rear].qx;
data[k].y=q[rear].qy;
data[k].z=q[rear].qz;
rear=q[rear].pre;
}
if(k>)
cout<<k<<' '<<"steps"<<endl;
else
cout<<k<<' '<<"step"<<endl;
cout<<"step0:"<<' '<<xmax<<' '<<''<<' '<<''<<endl;
for(int i=k;i>=;i--)
{
cout<<"step"<<k-i+<<':'<<' '<<data[i].x<<' '<<data[i].y<<' '<<data[i].z<<endl;
}
}
else
{
cout<<"No Solution"<<endl;
}
return ;
}
最后，还要感谢YYL大神的不啬指教以及xaero的ppt。
这是我的第一篇博文，欢迎各位大神的指点。
最新文章
- C++常见问题: 字符串分割函数 split
- C89和C99区别--简单总结
- linux init.d脚本编写模板
- 最好的Java IDE之争：Eclipse PK IntelliJ IDEA
- [Bhatia.Matrix Analysis.Solutions to Exercises and Problems]ExI.1.1
- 达到XML简单的动态配置
- Spring如何管理Session【转贴】
- mysql（2）—— 由笛卡尔积现象分析数据库表的连接
- AJAX的优点 个人理解记录
- web：频繁刷新浏览器的页面【小工具】
- Oracle Index 索引无效原因
- 存储opline的内存地址可以实时跟踪opcode的执行
- 笔试题——C++后序字符比较
- JS如何利用定时器实现长按事件
- Linq中的group by多表多字段
- 关于 <mvc:argument-resolvers> 的一次使用记录
- angular项目中使用jQWidgets
- MySQL 5.6/5.7 linux常见安装（tar，yum，script）
- div+css显示两行或三行文字
- nginx 用法