首页 > > 网络编程 > Php编程 >

Openjudge 2971:抓住那头牛&&P1…

2018-10-14 10:48:54来源：博客园阅读 ()

蒟蒻的第一次发题解

经过了深思熟虑

选中了一道经典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

样例输出

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

本蒟蒻个人认为这道题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; 
}

题目分割线~~~

关于这只牛

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

题目描述

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

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

输入输出格式

输入格式：

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

输出格式：

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

输入输出样例

输入样例#1：复制

1 
5 17

输出样例#1：复制

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

代码如下

#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;
}