gaoyangyang @ 2024-07-20 10:35:27
#include<bits/stdc++.h>
using namespace std;
short int n;
short int t[50001],x[50001],y[50001];
short int dx[4]={1,0,-1,0};
short int dy[4]={0,1,0,-1};
short int a[400][400];
struct node
{
short int x,y,t; short int pre;
}que[17000000];
int main()
{
cin>>n;
memset(a,-1,305*305);
for (int i=0; i<n; i++)
{
cin>>x[i]>>y[i]>>t[i];
if(a[x[i]][y[i]]==-1||a[x[i]][y[i]]>t[i])
a[x[i]][y[i]]=t[i];
if(x[i]-1>=0&&(a[x[i]-1][y[i]]==-1||a[x[i]-1][y[i]]>t[i]))
a[x[i]-1][y[i]]=t[i];
if(y[i]-1>=0&&(a[x[i]][y[i]-1]==-1||a[x[i]][y[i]-1]>t[i]))
a[x[i]][y[i]-1]=t[i];
if(a[x[i]+1][y[i]]==-1||a[x[i]+1][y[i]]>t[i])
a[x[i]+1][y[i]]=t[i];
if(a[x[i]][y[i]+1]==-1||a[x[i]][y[i]+1]>t[i])
a[x[i]][y[i]+1]=t[i];
}
if (a[0][0]==-1)
{
cout<<0;
return 0;
}
int head,tail;
head=0;tail=1;
que[tail].x=0;
que[tail].y=0;
que[tail].t=0;
que[tail].pre=0;
while (head<tail)
{
head++;
for (int i=0;i<4;i++)
{
int xx=que[head].x+dx[i];
int yy=que[head].y+dy[i];
if (xx>=0 and yy>=0 and (que[head].t+1<a[xx][yy] or a[xx][yy]==-1))
{
tail++;
que[tail].x=xx;
que[tail].y=yy;
que[tail].t=que[head].t+1;
que[tail].pre=head;
if (a[que[tail].x][que[tail].y]==-1)
{
cout<<que[tail].t; return 0;
}
}
}
}
cout<<-1;
return 0;
}
MLE 了....报错
by gaoyangyang @ 2024-07-20 10:35:51
还有RE