哎呀,做了1天的bfs,居然最后以后6个测试点tle告终(其余ac,56分)
查看原帖
哎呀,做了1天的bfs,居然最后以后6个测试点tle告终(其余ac,56分)
349994
gztony楼主2021/1/15 15:55

有哪位大神帮我看一下哪里需要优化,本咸鱼已经努力优化一次了!(使用了布尔型防重复走路数组)

#include<bits/stdc++.h>
using namespace std;
struct node{
	int x,y,t;
};
queue<node> walk;
int farm[305][305],meteor[50000][3],m;
const int dx[4]={-1,1,0,0},dy[4]={0,0,-1,1};
bool vis[305][305];
void bfs(){
	int i,j,x,y,t,tx,ty;
	node tmp,cur;
	tmp.x=0;
	tmp.y=0;
	tmp.t=0;
	walk.push(tmp);
	while(!walk.empty()){
		cur=walk.front();
		x=cur.x;
		y=cur.y;
		t=cur.t;
		vis[x][y]=true;
		//cout<<x<<" "<<y<<" "<<t<<endl;
		if(farm[x][y]==0){
			cout<<t;
			return;
		}
		for(i=0;i<m;i++){
			if(t==meteor[i][2]){
				tx=meteor[i][0];
				ty=meteor[i][1];
				farm[tx][ty]=1;
				//cout<<tx<<" "<<ty<<endl;
				for(j=0;j<4;j++){
					//cout<<" "<<tx+dx[j]<<" "<<ty+dy[j]<<endl;
					if(tx+dx[j]>=0&&ty+dy[j]>=0)
						farm[tx+dx[j]][ty+dy[j]]=1;
				}
			}
		}
		/*for(i=0;i<4;i++){
			for(int j=0;j<4;j++){
				cout<<farm[i][j]<<"\t";
			}
			cout<<endl;
		}*/
		if(farm[x][y]==1){
			/*cout<<-1;
			return;*/
			//cout<<"boom"<<endl;
			walk.pop();
			continue; 
		}
		for(i=0;i<4;i++){
			tx=x+dx[i];
			ty=y+dy[i];
			if(tx>=0&&ty>=0){
				if(farm[tx][ty]!=1&&!vis[tx][ty]){
					tmp.x=tx;
					tmp.y=ty;
					tmp.t=t+1;
					walk.push(tmp);
				}
			}
		}
		//t++;
		walk.pop();
	}
	cout<<-1;
}
int main(){
	int i,j,x,y;
	cin>>m;
	for(i=0;i<m;i++){
		cin>>meteor[i][0]>>meteor[i][1]>>meteor[i][2];
		x=meteor[i][0];
		y=meteor[i][1];
		farm[x][y]=-1;
		for(j=0;j<4;j++){
			//cout<<x+dx[j]<<" "<<y+dy[j]<<endl;
			if(x+dx[j]>=0&&y+dy[j]>=0)
				farm[x+dx[j]][y+dy[j]]=-1;
		}
	}
	bfs();
	return 0;
}

另外加注释的地方是用来调试的,供大家使用(微笑)(明明是懒得删)

2021/1/15 15:55
加载中...