求求大佬,救救孩子
查看原帖
求求大佬,救救孩子
505353
Ychensanyuan楼主2021/5/26 00:02

萌新,不太懂 这个题我在自己的软件上运行结果是正确的,但是在洛谷上全部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;	 
}
2021/5/26 00:02
加载中...