Luolity @ 2024-03-15 20:03:19
#include <bits/stdc++.h>
using namespace std;
const int N = 700;
struct node {
int x, y, step;
};
int dirX[5] = {0,0,0,1,-1}, dirY[5] = {0,1,-1,0,0};
int drop[N][N];
int v[N][N];
queue<node> q;
int cnt;
int main() {
int n; cin >> n;
memset(drop,-1,sizeof(drop));
for(int i = 0; i < n; i++){
int x, y, t; cin >> x >> y >> t;
for(int j = 0; j < 5; j++){
int xx = x + dirX[j]; int yy = y + dirY[j];
if(xx < 0 || yy < 0) continue;
if(drop[xx][yy]==-1 || drop[xx][yy] > t) drop[xx][yy] = t;
}
}
for(int i = 0; i < n; i++){
for(int j = 0; j < n; j++){
if(drop[i][j]==-1) drop[i][j] = 99999;
}
}
q.push((node){0,0,0});
v[0][0] = 1;
while(!q.empty()){
node temp = q.front();
cnt = temp.step;
q.pop();
if(drop[temp.x][temp.y] == 99999){
cout << cnt << endl;
return 0;
}
for(int i = 1; i < 5; i++){
int xx = temp.x + dirX[i]; int yy = temp.y + dirY[i];
if(xx < 0 || yy < 0 || v[xx][yy]) continue;
if(drop[xx][yy] <= cnt+1) continue;
v[xx][yy] = 1;
q.push((node){xx,yy,cnt+1});
}
}
cout << -1 << endl;
return 0;
}
by Bz_QC @ 2024-03-15 21:16:50
你把前n行前n列的drop中为-1的赋值为99999,但n能达到50000啊,这还不越界RE,应该把n改为N