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 流星的数组开太小了,一共有
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 是的,非常感谢