大佬们救救孩子吧,注释打好了,最后两个点RE
查看原帖
大佬们救救孩子吧,注释打好了,最后两个点RE
844773
dysprositos楼主2023/3/18 21:41

自己已经试过了,如果二维数组开300300大概会re最后5个,但是我开到2000020000只会re最后两个。 球球大佬救救+

#include<iostream>
#include<queue>
#include<climits>
#include<algorithm>

using namespace std;
const int N=20000,M=1e5;
int g[N][N],dx[5]={1,-1,0,0,0},dy[5]={0,0,1,-1,0};
int m,t1;
queue<pair<int,int>> q;

class meteors
{
	public:
		int t,x,y;
}me[N];

bool cmp(meteors a,meteors b)
{
	if(a.t<=b.t)return true;
	else return false;
}

void destory(int x,int y)//流星摧毁的地方
{
	for(int i=0;i<5;i++)
	{
		int a=x+dx[i],b=y+dy[i];
		if(a>=0&&a<=302&&b>=0&&b<=302)
		g[a][b]=-1;
	}
}

void bfs()
{
	int k=q.size();
	t1++;
	
	while(k--)
	{
		auto t=q.front();
		q.pop();
		
		if(g[t.first][t.second]>=0)//若该起点没被砸,就再存一次,因为上面遍历时把他删了
		{
			q.push(t);
		}
		
		for(int i=0;i<4;i++)
		{
			int a=t.first+dx[i],b=t.second+dy[i];
			if(a>=0&&a<=302&&b>=0&&b<=302&&!g[a][b])
			{
				g[a][b]=t1;
				q.push({a,b});
			}
		}
	}
}
int main()
{
	ios::sync_with_stdio(false);
	cin.tie();
	
	q.push({0,0});
	
	cin >> m;
	int X,Y;
	for(int i=0;i<m;i++)//记录所有流星坐标、时间
	{
		cin >> me[i].x >> me[i].y >> me[i].t;
	}
	
	sort(me,me+m,cmp);
	
	
	for(int i=0;i<m;i++)//对过程的模拟,如第一颗两秒砸地,
	//先dfs零到一秒,零到二秒时先让流星砸了再dfs零到二秒
	{
		while(t1<me[i].t-1)
		{
			bfs();
		}
		destory(me[i].x,me[i].y);
	}
	
	bfs();//最后一颗流星砸了后没有进行搜索,再搜一次


	//没地儿就-1
	if(q.size()==0)
	{
		cout << "-1";
		return 0;
	}
	//找最小
	int x=INT_MAX;
	int cnt=q.size();
	for(int i=0;i<cnt;i++)
	{
		x=min(x,g[q.front().first][q.front().second]);
		q.pop();
	}

	cout << x;
}
2023/3/18 21:41
加载中...