【C# 每日一题1】猫捉老鼠

Description



猫和老鼠在一条直线上，猫当然想抓住老鼠，而老鼠想逃回自己的家（在直线的某一点）

老鼠每次只能在直线上走一步，前进一个坐标

而猫有两种方法



1:在直线上走一步:前进一个坐标或后退一个坐标

2：往前跳一步，猫每次跳得距离等于猫当前坐标值



Input



第一行输入一个n，表示有几组测试数据

每组测试数据输入l表示老鼠的家的坐标（2<=l<=10000），x表示猫当前坐标，y表示老鼠当前坐标



Output



每组测试数据输出一个整数表示猫最少要几步才能抓住老鼠

如果猫抓不到老鼠则输出-1



你可以认为老鼠每次行动都在猫之前



Sample Input



1

100

20 88

Sample Output



6

C#区每日一题，周一至周五发表，希望大家支持

------解决方案--------------------

引用:

你可以认为老鼠每次行动都在猫之前

那么，猫在哪个时间点呢做决定是走还是跳？老鼠移动前还是移动后？
------解决方案--------------------
感觉上用2进制方便点
------解决方案--------------------

int dest,beginmouse,begincat;

struct _node
{
int catpos;
int mousepos;
};

_node queue[10000000];
int head,tail;

int step;
int minstep;

void Run()
{
int casenum;
scanf("%d",&casenum);
while(casenum--)
{
scanf("%d %d %d",&dest,&begincat,&beginmouse);
head = tail = 0;
step = -1;
minstep = -1;
if(begincat >= beginmouse)
{
if((begincat-beginmouse)%2 == 0)step = (begincat-beginmouse)/2;
}
else
{
queue[0].catpos = begincat;
queue[0].mousepos = beginmouse;
head = 0;tail = 1;
}
while(head < tail)
{
if(queue[head].mousepos-queue[0].mousepos >= minstep && minstep != -1)
{
head++;
continue;
}
//分三种情况
//1 猫后退一步
queue[tail].mousepos = queue[head].mousepos+1;
queue[tail].catpos = queue[head].catpos-1;
if(queue[tail].mousepos != dest)tail++;

//2 猫前进一步
queue[tail].mousepos = queue[head].mousepos+1;
queue[tail].catpos = queue[head].catpos+1;
if(queue[tail].mousepos != dest)tail++;

//猫前跳一步
int curmouse = queue[tail].mousepos = queue[head].mousepos+1;
int curcat = queue[tail].catpos = queue[head].catpos*2;
if(curcat >= curmouse)
{
if((curcat-curmouse)%2 == 0 && queue[tail].mousepos+(curcat-curmouse)/2 <= dest)
{
// printf("%d %d\n",queue[tail].mousepos,queue[tail].catpos);
step = queue[tail].mousepos-queue[0].mousepos+(curcat-curmouse)/2;
if(step < minstep 
------解决方案--------------------
 minstep == -1)minstep = step;
}
}
else tail++;
head++;
}
printf("%d\n",minstep);
}
}


int main()
{
Run();
while(1);
return 0;
}

------解决方案--------------------
时间有限只写了 
猫>鼠>家这种情况的
鼠>猫>家
猫>家>鼠
家>鼠>猫
家>猫>鼠
鼠>家>猫 都差不多

winForm 做的小动画

        private void MSGame()