首页
学习
活动
专区
工具
TVP
发布
社区首页 >专栏 >农夫与牛(STL-Queue、广度优先搜索)

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

作者头像
ACM算法日常
发布2018-12-28 14:21:01
6500
发布2018-12-28 14:21:01
举报
文章被收录于专栏:ACM算法日常ACM算法日常

农夫与牛

现有一农夫和一母牛,假设农夫和母牛都站在一条数轴上,农夫开始的位置为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;
}
本文参与 腾讯云自媒体分享计划,分享自微信公众号。
原始发表:2018-12-20,如有侵权请联系 cloudcommunity@tencent.com 删除

本文分享自 ACM算法日常 微信公众号,前往查看

如有侵权,请联系 cloudcommunity@tencent.com 删除。

本文参与 腾讯云自媒体分享计划  ,欢迎热爱写作的你一起参与!

评论
登录后参与评论
0 条评论
热度
最新
推荐阅读
领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档