基本算法练习__约会问题

基本算法练习__约会问题

这类问题与迷宫问题的走法有些类似，即经过多少步是否可以从起点到终点的问题。

代码如下：

#include using namespace std;int main(){ int a,b,s; cin>>a>>b>>s; int sum = abs(a)+abs(b); if(sum>s){ cout<<"No"; }else if((sum-s)%2==0){ cout<<"Yes"; }else{ cout<<"No"; } return 0;}

分析:

首先，将终点的x,y值 平铺在 一维的数轴上。（因为每次移动为1个长度，平铺只会丢失方向信息，但是不会丢失长度信息）

在一维上后，二者的长度和(记为sum)与 步数之差的2的余数必须为0的原因：在当前的一维数组上，不同的两个线段总可以经过偶数个(-1+1=0)进行调和。 所以，使得条件满足。

sum>s为no的原因在于，sum在此时为绝对长度，s小于绝对长度后，不可能找到合适的(-1+1=0)进行调和。

注意，这种方法实际上就省去了很多具体情况的考虑，而是以总体进行考虑。

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。