dysprositos @ 2023-03-18 21:41:22
自己已经试过了,如果二维数组开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;
}
by dysprositos @ 2023-03-18 22:01:29
呜呜呜,对不起,你们骂我吧。我这道题写太久写昏了。最后我的流星结构数组用的N,改回M就好了 二维数组看来不用开这么大,稍微过300就行了,大家别忘了流星的范围时1e5