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 RainandBOW @ 2023-01-23 16:01:27
改成300过不了,必须要开大
if(x1>=0 && x1<=300 && y1>=0 && y1<=300 && !st[x1][y1] && (g[x1][y1]==-1 || t1<g[x1][y1]))
{
st[x1][y1]=1;
q.push({x1,y1});
d[x1][y1]=t1;
}
by OldDriverTree @ 2023-01-23 16:35:10
@RainandBOW
数组越界了,应该全
初始化时建议使用 memset
,用 for 循环边界条件改成 i<N
和 j<N
数组至少应该开 301
by RainandBOW @ 2023-01-23 16:48:34
@guoxiangyu66 我数组开了310,还能re?
by OldDriverTree @ 2023-01-23 16:49:40
@RainandBOW 初始化改成 i<N
和 j<N
就完全正确了
by RainandBOW @ 2023-01-23 16:50:56
@guoxiangyu66 我想问的是我dfs判断边界条件为啥300不行,必须要开大,题目不就是300
by RainandBOW @ 2023-01-23 16:52:36
@guoxiangyu66 wa最后一个点
by OldDriverTree @ 2023-01-23 16:53:34
@RainandBOW 哦,看错了
by RainandBOW @ 2023-01-23 16:53:35
@guoxiangyu66 <和<=明显就是<=更好
by OldDriverTree @ 2023-01-23 16:55:18
@RainandBOW
但是使用 <=
正常情况下都会 RE
因为数组的下标是从 0~N-1 的
by RainandBOW @ 2023-01-23 16:56:00
@guoxiangyu66 我N开到310明显比题目给的300要大10还能re?