搜公众号
推荐 原创 视频 Java开发 开发工具 Python开发 Kotlin开发 Ruby开发 .NET开发 服务器运维 开放平台 架构师 大数据 云计算 人工智能 开发语言 其它开发 iOS开发 前端开发 JavaScript开发 Android开发 PHP开发 数据库
Lambda在线 > 农夫与牛(STL-Queue、广度优先搜索)

农夫与牛(STL-Queue、广度优先搜索)

2018-12-21
举报

农夫与牛


现有一农夫和一母牛,假设农夫和母牛都站在一条数轴上,农夫开始的位置为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;
}

温馨提示




点赞的时候,请宠溺一点


版权声明:本站内容全部来自于腾讯微信公众号,属第三方自助推荐收录。《农夫与牛(STL-Queue、广度优先搜索)》的版权归原作者「ACM算法日常」所有,文章言论观点不代表Lambda在线的观点, Lambda在线不承担任何法律责任。如需删除可联系QQ:516101458

文章来源: 阅读原文

相关阅读

举报