欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  IT编程

Openjudge 2971:抓住那头牛&&P1588 丢失的牛

程序员文章站 2022-06-27 14:06:32
蒟蒻的第一次发题解 经过了深思熟虑 选中了一道经典BFS(队列)题 2971:抓住那头牛 总时间限制: 2000ms 内存限制: 65536kB描述 农夫知道一头牛的位置,想要抓住它。农夫和牛都位于数轴上,农夫起始位于点N(0<=N<=100000),牛位于点K(0<=K<=100000)。农夫有两 ......

蒟蒻的第一次发题解

经过了深思熟虑

选中了一道经典bfs(队列)题

2971:抓住那头牛

总时间限制: 
2000ms
 
内存限制: 
65536kb
描述

农夫知道一头牛的位置,想要抓住它。农夫和牛都位于数轴上,农夫起始位于点n(0<=n<=100000),牛位于点k(0<=k<=100000)。农夫有两种移动方式:

1、从x移动到x-1或x+1,每次移动花费一分钟
2、从x移动到2*x,每次移动花费一分钟
 
假设牛没有意识到农夫的行动,站在原地不动。农夫最少要花多少时间才能抓住牛?

 

输入
两个整数,n和k
输出
一个整数,农夫抓到牛所要花费的最小分钟数
样例输入
5 17
样例输出
4

 

 

看到这道题首先想到的是搜索算法

本蒟蒻个人认为这道题bfs可以solve problem easily

大致思想如下:

用一个长的队列来记录能到达的距离

令相同时间走到的距离在同一深度

代码中,第i个数的深度即dep[i]

所以第一个值为k的数的深度就是答案

不多说了

上代码

 

#include<iostream>//朴素的头文件 
using namespace std;
int n,k,que[100005],dep[100005],head,tail; //标准的变量名 不用解释吧
bool a[100005];//确保步数最少 
int main()
{
    cin>>n>>k;
    if(n>=k)
    {
        cout<<n-k; //后退只能一步一步走 
        return 0;
    }
    a[n]=true;head=1,tail=1;
    dep[1]=0;que[1]=n;
    while(head<=tail)
    {
        if(que[head]+1==k||que[head]-1==k||que[head]*2==k)
        //接下来的操作会使队列多三个元素,所以要事先判断 
        {
            cout<<dep[head]+1; 
            return 0;//完美结束!!! 
        }
        if(!a[que[head]+1]&&que[head]+1<100005)//走法1 
        {
            tail++;
            que[tail]=que[head]+1;
            dep[tail]=dep[head]+1;
            a[que[tail]]=true; 
        }
        if(!a[que[head]-1]&&que[head]-1>=0)//走法2 
        {
            tail++;
            que[tail]=que[head]-1;
            dep[tail]=dep[head]+1;
            a[que[tail]]=true;     
        }
        if(!a[que[head]*2]&&que[head]*2<100005)//走法3 
        {
            tail++;
            que[tail]=que[head]*2;
            dep[tail]=dep[head]+1;
            a[que[tail]]=true; 
        }
        head++;//移动头指针 
    } 
    return 0; 
}

 

 


 

题目分割线~~~

 

 

关于这只牛

我大洛谷上也有一道相似的黄题

p1588 丢失的牛

题目描述

fj丢失了他的一头牛,他决定追回他的牛。已知fj和牛在一条直线上,初始位置分别为x和y,假定牛在原地不动。

fj的行走方式很特别:他每一次可以前进一步、后退一步或者直接走到2*x的位置。计算他至少需要几步追上他的牛。

输入输出格式

输入格式:

 

第一行为一个整数t(≤10),表示数据组数;接下来每行包含一个两个正整数x和y(0<x,y≤10^5),分别表示fj和牛的坐标。

 

输出格式:

 

对于每组数据,输出最少步数。

 

输入输出样例

输入样例#1: 复制
1 
5 17
输出样例#1: 复制
4

这道题只需把以上代码写到函数里就好

代码如下

#include<iostream>
#include<cstring>//本人不喜用万能头文件 
using namespace std;
int n,k,que[200005],dep[200005],head,tail;
bool a[200005]; //洛谷的数据比较苛刻,数组范围需要改一改 
void bfs()
{ 
    if(n>=k)
    {
        cout<<n-k<<endl; //后退只能一步一步走 
        return;
    }
    a[n]=true;head=1,tail=1;
    dep[1]=0;que[1]=n;
    while(head<=tail)
    {
        if(que[head]+1==k||que[head]-1==k||que[head]*2==k)
        //接下来的操作会使队列多三个元素,所以要事先判断 
        {
            cout<<dep[head]+1<<endl; 
            return; 
        }
        if(!a[que[head]+1]&&que[head]+1<100005)//走法1 
        {
            tail++;
            que[tail]=que[head]+1;
            dep[tail]=dep[head]+1;
            a[que[tail]]=true; 
        }
        if(!a[que[head]-1]&&que[head]-1>=0)//走法2 
        {
            tail++;
            que[tail]=que[head]-1;
            dep[tail]=dep[head]+1;
            a[que[tail]]=true;     
        }
        if(!a[que[head]*2]&&que[head]*2<100005)//走法3 
        {
            tail++;
            que[tail]=que[head]*2;
            dep[tail]=dep[head]+1;
            a[que[tail]]=true; 
        }
        head++;//移动头指针 
    } 
}
int main()
{
    int s,i;
    cin>>s;
    for(i=1;i<=s;i++)
    {
        cin>>n>>k;
        memset(que,0,sizeof(que));
        memset(dep,0,sizeof(dep));
        memset(a,0,sizeof(a));
        bfs();
    }
    return 0;
}

 

好了,本题解完美结束