63分BFS,TLE求助
查看原帖
63分BFS,TLE求助
352426
就决定是你辣楼主2022/9/8 17:17

rt,是不是状态剪枝出了问题TAT

#include<bits/stdc++.h>
using namespace std;
bool p[305][305];
bool d[305][305];
bool e[305][305];
struct node{
	int t,x,y;
	bool operator<(const node &a)const{return t<a.t;}
}star[50005];
queue<node>q;
int main(){
	int m;
	scanf("%d",&m);
	for(int i=1;i<=m;i++){
		scanf("%d%d%d",&star[i].x,&star[i].y,&star[i].t);
	}
	sort(star+1,star+1+m);
	for(int j=1;j<=m;j++){
		d[star[j].x][star[j].y]=1;
		d[star[j].x+1][star[j].y]=1;
		d[star[j].x-1][star[j].y]=1;
		d[star[j].x][star[j].y+1]=1;
		d[star[j].x][star[j].y-1]=1;
	}
	q.push(node{0,0,0});
	int j=1;
	while(!q.empty()){
		int x=q.front().x;
		int y=q.front().y;
		int t=q.front().t;
		e[x][y]=1;
		q.pop();
		while(t>=star[j].t&&j<=m){
			p[star[j].x][star[j].y]=1;
			p[star[j].x+1][star[j].y]=1;
			if(star[j].x-1>=0)p[star[j].x-1][star[j].y]=1;
			p[star[j].x][star[j].y+1]=1;
			if(star[j].y-1>=0)p[star[j].x][star[j].y-1]=1;
			j++;
		}
		if(y<0||x<0||p[x][y]){
			continue;
		}
		if(!d[x][y]){
			//cout<<x<<" "<<y<<endl; 
			cout<<t<<endl;
			return 0;
		}
		if(!e[x][y+1])q.push(node{t+1,x,y+1});
		if(y>0||!p[x][y-1]||!e[x][y-1])q.push(node{t+1,x,y-1});
		if(!e[x+1][y])q.push(node{t+1,x+1,y});
		if(x>0||!p[x-1][y]||!e[x-1][y])q.push(node{t+1,x-1,y});
	}
	cout<<-1<<endl;
} 
2022/9/8 17:17
加载中...