求求大佬,救救孩子

P2895 [USACO08FEB] Meteor Shower S

Ychensanyuan @ 2021-05-26 00:02:35

萌新,不太懂 这个题我在自己的软件上运行结果是正确的,但是在洛谷上全部WA了 我开了O2后AC了一半,是什么原因呢? 拜托大佬帮帮小萌新

#include<bits/stdc++.h>
using namespace std;

//通过结构体储存bessie的位置 
struct b{
    int x;
    int y;
    int step;
};

queue<b> state;

int main()
{
    int m;
    int meteor[300][3];
    int map1[400][400];
    int map2[400][400];

    int dx[4]={1,-1,0,0};
    int dy[4]={0,0,1,-1};

    int star_x,star_y;
    int bx,by,step;
    int i,j;
    int flag;

    memset(map1,0,sizeof(map1));
    memset(map2,0,sizeof(map2));
    memset(meteor,0,sizeof(meteor));

    //对输入的数据进行存储 
    scanf("%d",&m);

    for(i=0;i<m;i++){
        for(j=0;j<3;j++){
            scanf("%d",&meteor[i][j]);
        }
    }

    //得到最终的地图
    for(i=0;i<m;i++){
        star_x=meteor[i][0];
        star_y=meteor[i][1];
        //如果刚开始已经有流星落下

        for(j=0;j<4;j++){ 
            if(meteor[i][2]==0){
                map1[star_x][star_y]=1;
                map1[star_x+dx[j]][star_y+dy[j]]=1;
            }
            map2[star_x][star_y]=1;
            map2[star_x+dx[j]][star_y+dy[j]]=1;
        }
    }

    //将起始位置入队 
    b start;
    start.x=0;
    start.y=0;
    start.step=0;
    state.push(start);

    while(!state.empty()){

        bx=state.front().x;
        by=state.front().y;
        step=state.front().step;

        //到达了安全区域 
        if(map2[bx][by]==0){
            flag=1;
            printf("%d",step);
            break;
        }

        //没有到达安全区域 
        else{

            //在进行BFS前,先要对地图进行处理
            for(i=0;i<m;i++){

                //如果恰好将有流星落下 ,更新相关地图 
                if(meteor[i][2]==step+1){
                    star_x=meteor[i][0];
                    star_y=meteor[i][1];
                    //落下处,更新地图 
                    map1[star_x][star_y]=1;

                    //落下周围更新地图 
                    for(j=0;j<4;j++){
                        map1[star_x+dx[j]][star_y+dy[j]]=1;
                    }
                }   
            }

            //进行四个方向试探
            for(i=0;i<4;i++){
                if(map1[bx+dx[i]][by+dy[i]]==0&&bx+dx[i]>=0&&by+dy[i]>=0){

                    //对走过的路进行标记,避免往回走 
                    map1[bx+dx[i]][by+dy[i]]=2; 
                    //入队
                    b temp;
                    temp.x=bx+dx[i];
                    temp.y=by+dy[i];
                    temp.step=step+1;
                    state.push(temp);

                }
            }

            //结束了出队
            state.pop(); 

        }   

    }

    if(flag==0){
        printf("-1");
    }
return 0;    
}

by 阿丑 @ 2021-05-26 07:18:10

@Ychensanyuan 流星的数组开太小了,一共有 50000 颗流星 qwq


by SunsetSamsara @ 2021-05-26 07:43:20

另外数组可能越界,访问到不该访问的数据


by Ychensanyuan @ 2021-05-26 11:33:11

@阿丑 非常感谢,已经全部AC了


by Ychensanyuan @ 2021-05-26 11:34:02

但是为什么我没有开O2优化,就会除了输出-1的全部WA呢?


by Ychensanyuan @ 2021-05-26 11:46:33

@Canstant0x5F3759DF 请问大佬,哪一个数组可能越界呢?


by SunsetSamsara @ 2021-05-26 13:22:34

比如在这里,


    //得到最终的地图
    for(i=0;i<m;i++){
        star_x=meteor[i][0];
        star_y=meteor[i][1];
        //如果刚开始已经有流星落下

        for(j=0;j<4;j++){ 
            if(meteor[i][2]==0){
                map1[star_x][star_y]=1;
                map1[star_x+dx[j]][star_y+dy[j]]=1;//这里
            }
            map2[star_x][star_y]=1;
            map2[star_x+dx[j]][star_y+dy[j]]=1;
        }
    }

万一star_x在边界上的时候就可能越界


by Ychensanyuan @ 2021-05-26 14:44:13

@Canstant0x5F3759DF 是的,非常感谢


|