Catch the cow(POJ3278) 编译器上没问题, OJ上一直runtime error?

Question

原题网址

下面是我已经在编译器上通过的代码,但是OJ上始终会RE
(使用的是广度优先搜索的方法)

#include <stdio.h>
#include <stdlib.h>

#define MAX_N 100000

int n, k, ans;
int que[MAX_N+10][2];
int vis[MAX_N+10];

int head, tail;

void bfs( int x);
void enqueue ( int x, int time);


int main(void)
{   
    scanf("%d %d", &n, &k);
    if( n>k)
    {
        ans = n-k;
    }
    else
    {
        bfs(n);
    }

    printf("%d\n", ans);

    return 0;
}

void bfs( int x)
{
    enqueue(x, 0);
    vis[x] = 1;

    while(head<tail)
    {
        int i, nowx, nowtime;
        nowx = que[head][0];
        nowtime = que[head][1];
        head ++;

        if( nowx == k)
        {
            ans = nowtime;
            break;
        }

        for( i=1; i<=3; i++)
        {
            if( i==1 && vis[nowx-1]!=1 && nowx-1>=0 && nowx-1 <= MAX_N)
            {
                enqueue( nowx-1, nowtime+1);
                vis[nowx-1] = 1;

            }
            if( i==2 && vis[nowx+1]!=1 && nowx+1>=0 && nowx+1 <= MAX_N)
            {
                enqueue( nowx+1, nowtime+1);
                vis[nowx+1] = 1;
            }
            if( i==3 && vis[nowx*2]!=1 && nowx*2>=0 && nowx*2 <= MAX_N)
            {
                enqueue( nowx*2, nowtime+1);
                vis[nowx*2] = 1;
            }
        }
    }
}

void enqueue( int x, int time)
{
    que[tail][0] = x;
    que[tail][1] = time;
    tail ++;
}

一开始查了之后说可能是什么栈空间不够,就尝试了一下动态分配空间
(萌新还没学指针,就在网上照猫画虎贴了进去), 但是数字只要大一点程序就无法输出结果
更改后的代码如下:

#include <stdio.h>
#include <stdlib.h>

#define MAX_N 100001

int n, k, ans;
//int que[MAX_N+10][2];     /*之前的方案,但同样RE了,可能是空间不足(?),所以尝试如下动态分配的方法*/ 
//int vis[MAX_N+10];

int head, tail;

void bfs( int x, int **que, int *vis);
void enqueue ( int x, int time, int **que);


int main(void)
{   
    int **que;
    int i, j;
    int *vis;

    que = (int**)malloc(sizeof(int*)*MAX_N);        //为两个数组分配空间 
    for( i=0; i<MAX_N; i++)
    {
        que[i] = (int*)malloc(sizeof(int)*2);
     } 

    vis = (int*)malloc(sizeof(int)*MAX_N);

    scanf("%d %d", &n, &k);
    if( n>k)
    {
        ans = n-k;
    }
    else
    {
        bfs(n, que, vis);           //进入深搜 
    }


    printf("%d\n", ans);

    return 0;
}

void bfs( int x, int **que, int *vis)
{
    enqueue(x, 0, que);
    vis[x] = 1;

    while(head<tail)
    {
        int i, nowx, nowtime;
        nowx = que[head][0];            //队列数据的取出 
        nowtime = que[head][1];
        head ++;

        if( nowx == k)              //结束条件 
        {
            ans = nowtime;
            break;
        }

        for( i=1; i<=3; i++)        //对三种可能进行遍历 
        {
            if( i==1 && vis[nowx-1]!=1 && nowx-1>=0 && nowx-1 <= MAX_N)
            {
                enqueue( nowx-1, nowtime+1, que);
                vis[nowx-1] = 1;

            }
            if( i==2 && vis[nowx+1]!=1 && nowx+1>=0 && nowx+1 <= MAX_N)
            {
                enqueue( nowx+1, nowtime+1, que);
                vis[nowx+1] = 1;
            }
            if( i==3 && vis[nowx*2]!=1 && nowx*2>=0 && nowx*2 <= MAX_N)
            {
                enqueue( nowx*2, nowtime+1, que);
                vis[nowx*2] = 1;
            }
        }
    }
}

void enqueue( int x, int time, int **que)   //队列数据的写入 
{
    que[tail][0] = x;
    que[tail][1] = time;
    tail ++;
}

请教一下大佬们上面RE的原因到底是什么, 还有下面的动态分配有什么问题,感激不尽

Answer 1

因为nowx*2后可能会超过MAX_N,所以VIS数组大小要定义成2*MAX_N