tangguochao @ 2021-12-01 22:09:04
#include <bits/stdc++.h>
using namespace std;
int ti[400][400];
int ans[400][400];
int Ans=9999999;
int walk[4][2]={{-1,0},{1,0},{0,1},{0,-1}};
struct coord{
int x,y;
};
int main()
{
memset(ans,-1,sizeof (ans));
memset(ti,999999,sizeof (ti));
ans[0][0]=0;
int M;
cin >> M;
while (M--)
{
int x,y,t;
cin >>x >> y >> t;
printf("ok");
ti[x][y]=min(t,ti[x][y]);
for(int j=0;j<4;j++)
{
ti[x+walk[j][0]][y+walk[j][1]]=min(t,ti[x+walk[j][0]][y+walk[j][1]]);
}
}
printf("ok\n");
queue<coord>Q;
Q.push((coord){0,0});
while (!Q.empty())
{
int ux=Q.front().x;
int uy=Q.front().y;
int t=ans[ux][uy];
Q.pop();
for(int j=0;j<4;j++)
{
int x=ux+walk[j][0];
int y=uy+walk[j][1];
if (x < 0 ||x>300|| y < 0 ||y>300|| ans[x][y] != -1 || t +1>= ti[x][y])
continue;
ans[x][y]=t+1;
Q.push((coord){x,y});
}
}
for(int i=0;i<=305;i++)
{
for(int j=0;j<=305;j++)
{
if(ti[i][j]>5000&&ans[i][j]!=-1)
Ans=min(Ans,ans[i][j]);
}
}
if(Ans==999999)
puts("-1");
else
printf("%d",Ans);
return 0;
}