信息学奥赛 抓住那头牛 评测出错

Question

http://ybt.ssoier.cn:8088/problem_show.php?pid=1253
[题目描述]

农夫知道一头牛的位置，想要抓住它。农夫和牛都位于数轴上，农夫起始位于点N(0≤N≤100000)，牛位于点K(0≤K≤100000)。农夫有两种移动方式：
1、从X移动到X−1或X+1，每次移动花费一分钟
2、从X移动到2×X，每次移动花费一分钟
假设牛没有意识到农夫的行动，站在原地不动。农夫最少要花多少时间才能抓住牛？

[输入]

两个整数，N和K

[输出]

一个整数，农夫抓到牛所要花费的最小分钟数

[样例]

输入:5 17

输出:4

解释:从5到17的过程
5 > [-1] > 4 > [*2] > 8 > [*2] > 16 > [+1] > 17

[我的代码]

#include<iostream>
#include<cstdio>
using namespace std;
int UP(int n){return n+1;}
int DOWN(int n){return n-1;}
int FLY(int n){return n*2;}
int n,k,(*F[3])(int)={UP,DOWN,FLY},T=1,W,b[1000001];
struct node
{
    int n,l;
}Q[1000001],l;
int BFS()
{
    W++;
    Q[W].n=n;
    while(T<=W)
    {
        n=Q[T].n;
        l.l=Q[T].l+1;
        T++;
        for(int i=0;i<3;i++)
        {
            l.n=F[i](n);
            if(l.n==k)
            {
                return l.l;
            }
            if(b[l.n]==0 && l.n>=0 && l.n<=100000)
            {
                b[l.n]=1;
                W++;
                Q[W].n=l.n;
                Q[W].l=l.l;
            }
        }
    }
}
int main()
{
    cin>>n>>k;
    cout<<BFS();
}

[错误原因]

测试好好的,提交评测时就[运行时错误]

Answer 1

望采纳！！点击该回答右侧的“采纳”按钮即可采纳！！

您的代码中似乎并没有明显的语法错误。不过，有几点可以注意：

在主函数 main 中，变量 W 应该被初始化为 0，而不是 1。因为 W 用来记录队列 Q 的末尾位置，而队列 Q 的第一个元素的位置是 0。

在 BFS 函数中，当 l.n 等于 k 时，应该直接返回 l.l，而不是 return l.l;。

在 BFS 函数中，当 l.n 大于 100000 时，应该将 l.n<=100000 改为 l.n<=100000。

在 BFS 函数中，在循环体末尾应该添加一个大括号，否则会导致代码不能正常编译。

#include<iostream>
#include<cstdio>
using namespace std;
int UP(int n){return n+1;}
int DOWN(int n){return n-1;}
int FLY(int n){return n*2;}
int n,k,(*F[3])(int)={UP,DOWN,FLY},T=1,W,b[1000001];
struct node
{
    int n,l;
}Q[1000001],l;
int BFS()
{
    W=0;
    Q[W].n=n;
    while(T<=W)
    {
        n=Q[T].n;
        l.l=Q[T].l+1;
        T++;
        for(int i=0;i<3;i++)
        {
            l.n=F[i](n);
            if(l.n==k)
            {
                return l.l;
            }
            if(b[l.n]==0 && l.n>=0 && l.n<=100000)
            {
                b[l.n]=1;
                W++;
                Q[W].n=l.n;
                Q[W].l=l.l;
            }
        }
    }
}
int main()
{
    cin>>n>>k;
    cout<<BFS();
}