农夫与牛
现有一农夫和一母牛,假设农夫和母牛都站在一条数轴上,农夫开始的位置为N,母牛的位置为K。农夫有三种行动方式,每行动一次需要一秒钟时间,假设农夫的现在的位置为X,他可以向前走一格到X+1,也可以向后走一格走到X-1,他还可以传送!一下子走到了2*X。那么我们的问题是,假设母牛不会动,农夫最少需要多少秒才能抓到母牛?
输入:
输入包括两个整数,用空格隔开,分别为N和K。其中0<=N,K<=100000。
输出:
一个整数T,代表农夫所需的最少时间。
首先分析一下,有没有最小时间的算法:
若N=5,K=17,那么最后我们计算得到的应该是T=4。
1、假设我们采用全部往前走的策略,那么我们一共要走17-5=12步。
2、是不是只要乘得越多得到的步数就越少呢?因为我们一开始就让5×2=10,这样可以省去很多步骤 5→10→20→19→18→17
3、实际上有更优的策略! 5→10→9→18→17
由上面分析可知,没有一定的策略,使得时间一定最短。
此时可以考虑广度优先搜索,将农夫在每一步所走的策略都列举出来,生成一棵三叉正则完全树。用队列Queue存储这些结果,根据队列先进先出的特性,最先找到农夫到达奶牛的结果所花费的时间便是最短的时间。(广搜一般都用队列存储结果)
但是,由于广度优先搜索要列出所有的结果,因此容易超时。要对广搜做一定的优化,即剪枝处理(去掉一些没必要存储的结果)
本题优化如下:
1.当农夫的位置为0的时候,他只能往前走1。
2.当农夫的位置大于K时,他只能往后走1 。
3.如果某个位置农夫已经走过,那么农夫不用再走到该位置。
代码如下:
#include<iostream>
#include<queue>
#include <algorithm>
using namespace std;
int N,K;
struct point{ //当前状态,X为农夫当前的位置,T为农夫走过的次数
int X;
int T;
};
bool vis[200050];//用于标记该位置农夫是否走过
int main()
{
cin>>N>>K;
point a;
a.X=N;
a.T=0;
queue<point> que;
que.push(a);//将该节点(即初始状态)加入队列
for(int i=0;i<200050;i++)
vis[i]=0;
vis[N]=1;
while(!que.empty())
{
point temp=que.front();
que.pop();
if(temp.X==K)//如果农夫当前的位置就是K,那么输出T并退出程序。
{
cout<<temp.T<<endl;
break;
}
if(temp.X-1>=0&&vis[temp.X-1]==0)//如果往后走不是0,并且往后走的那个位置没有被走过,那么我们就把往后的情况加入到队列
{
point tt=temp;
tt.X--;//往后走
tt.T++;//时间加1
que.push(tt);//加入队列
vis[temp.X-1]=1;//标记为走过
}
if(temp.X<K&&vis[temp.X+1]==0)//往前走的情况
{
point tt=temp;
tt.X++;
tt.T++;
que.push(tt);
vis[temp.X+1]=1;
}
if(temp.X<K&&vis[temp.X*2]==0)//乘2的情况
{
point tt=temp;
tt.X*=2;
tt.T++;
que.push(tt);
vis[temp.X*2]=1;
}
}
return 0;
}