RainandBOW @ 2023-01-23 16:00:23
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define endl '\n'
typedef pair<int, int> PII;
typedef pair<string,int> PSI;
#define f first
#define s second
#define pb push_back
const int N = 310;
int g[N][N];//地图
bool st[N][N];
int d[N][N];
int n;
int dx[] = {0,-1, 0, 1, 0}, dy[] = {0,0, 1, 0, -1};
queue<PII>q;
void bfs()
{
q.push({0,0});
st[0][0]=1;
while(q.size())
{
auto t=q.front();
q.pop();
int t1=d[t.f][t.s]+1;
if(g[t.f][t.s]==-1)
{
cout<<d[t.f][t.s]<<endl;
return ;
}
for(int i=1;i<=4;i++)
{
int x1=t.f+dx[i],y1=t.s+dy[i];
if(x1>=0 && x1<=301 && y1>=0 && y1<=301 && !st[x1][y1] && (g[x1][y1]==-1 || t1<g[x1][y1]))
{
st[x1][y1]=1;
q.push({x1,y1});
d[x1][y1]=t1;
}
}
}
cout<<-1<<endl;
return ;
}
signed main()
{
ios::sync_with_stdio(false);
cin.tie(nullptr),cout.tie(nullptr);
cin>>n;
for(int i=0;i<=N;i++)
for(int j=0;j<=N;j++)
g[i][j]=-1;
for(int i=1;i<=n;i++)
{
int x,y,t;
cin>>x>>y>>t;
for(int j=0;j<5;j++)
{
int x1=x+dx[j],y1=y+dy[j];
if(x1>=0 && x1<=300 && y1>=0 && y1<=300 &&(g[x1][y1]==-1 || g[x1][y1]>t))
{
g[x1][y1]=t;
}
}
}
bfs();
return 0;
}
by OldDriverTree @ 2023-01-23 16:57:00
@RainandBOW 数组越界后正常情况下就会 RE
by RainandBOW @ 2023-01-23 17:03:06
@guoxiangyu66 不是re是wa呀
by RainandBOW @ 2023-01-23 17:05:01
@guoxiangyu66 我疑惑的地方是为啥dfs里面的x1,y1的范围不是到300而是要比300大