_rainbow_ @ 2022-08-16 14:45:45
#include<bits/stdc++.h>
#include<limits.h>
using namespace std;
int dx[4]={-1,0,1,0};
int dy[4]={0,1,0,-1};
int a[500][500],m,xi,yi,ti,nx,ny,nt,vis[500][500];
struct node{
int x,y,t;
};
queue<node> q;
node tmp;
int main(){
cin>>m;
for(int i=0;i<=305;i++){
for(int j=0;j<=305;j++){
a[i][j]=10000;
}
}
for(int i=1;i<=m;i++){
cin>>xi>>yi>>ti;
if(ti<a[xi][yi]){
a[xi][yi]=ti;
}
for(int j=0;j<4;j++){
if(ti<a[xi+dx[j]][yi+dy[j]]){
a[xi+dx[j]][yi+dy[j]]=ti;
}
}
}
tmp=(node){0,0,0};
q.push(tmp);
vis[0][0]=1;
while(!q.empty()){
tmp=q.front();
q.pop();
xi=tmp.x;
yi=tmp.y;
ti=tmp.t;
if(a[xi][yi]==10000){
break;
}
for(int i=0;i<4;i++){
nx=xi+dx[i];
ny=yi+dy[i];
nt=ti+1;
if(nx>=0&&ny>=0&&nt<a[nx][ny]&&vis[nx][ny]==0){
vis[nx][ny]=1;
q.push((node){nx,ny,nt});
}
}
}
if(a[xi][yi]==10000){
cout<<ti;
}
else{
cout<<-1;
}
return 0;
}
by Mynameisxu @ 2022-08-16 14:47:15
前排吃瓜
by JustinXiaoJunyang @ 2022-08-16 14:47:56
@rainbow 求关注~
会越界,数组开大点,开到 1000 可以了。
by JustinXiaoJunyang @ 2022-08-16 14:48:09
@Mynameisxu wyy jbl
by xiang314 @ 2022-08-16 14:59:46
??? 你这程序不是过的吗??? 我试了
by _rainbow_ @ 2022-08-16 15:02:01
@JustinXiaoJunyang 谢谢,已关注
by xiang314 @ 2022-08-16 15:03:11
点一下上面的O2优化
by _rainbow_ @ 2022-08-16 15:04:07
@HIM0315 谢谢
by Mynameisxu @ 2022-08-16 16:42:43
@JustinXiaoJunyang 。。。。。