YupenBob @ 2023-09-04 22:10:18
#include <bits/stdc++.h>
using namespace std;
const int N=350;
int n;
bool m[N][N];
int tmap[N][N];
int dx[5]={0, 0, 0, 1, -1};
int dy[5]={0, 1, -1, 0, 0};
int bdx[4]={0, 0, 1, -1};
int bdy[4]={1, -1, 0, 0};
bool vis[N][N];
struct node {
int x,y,t;
};
queue <node> que;
int main () {
memset(m,0,sizeof(m));
memset(tmap,0,sizeof(tmap));
scanf("%d",&n);
for (int i=0;i<n;i++) {
int x,y,t;
scanf("%d%d%d",&x,&y,&t);
for (int j=0;j<5;j++) {
int nx=x+dx[j];
int ny=y+dy[j];
if (0<=nx&&0<=ny) {
if (!m[nx][ny]) {
m[nx][ny]=1;
tmap[nx][ny]=t;
}
}
}
}
que.push((node) {0,0,0});
while (que.size()) {
node p=que.front();
que.pop();
for (int i=0;i<4;i++) {
int nx=bdx[i]+p.x;
int ny=bdy[i]+p.y;
int nt=1+p.t;
if (0<=nx&&0<=ny&&(!vis[nx][ny])) {
if (!m[nx][ny]) {
printf("%d",nt);
return 0;
}
else if (tmap[nx][ny]>nt) {
vis[nx][ny]=1;
que.push((node) {nx,ny,nt});
}
}
}
}
printf("-1");
return 0;
}