象龟迭戈 @ 2021-10-25 17:02:27
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cmath>
#include <vector>
#include <cstring>
#include <queue>
//#define MAXN
using namespace std;
typedef long long ll;
int m,d[305][305],timee[305][305];//d记录答案 timee记录(x,y)位置陨石砸落的最小时间
bool flag,v[305][305];//flag用来判断是否到达安全位置 v实现不走回头路
int ed[5][5]={
{},
{0,1,0},
{0,0,-1},
{0,-1,0},
{0,0,1},
};//四个方向
struct Node{
int x,y,ttime;
}pla;
queue<Node> q;
//const ll mod=
int read();
void bfs();
bool check(int x,int y,int z);
int main()
{
m=read();
for(int i=0;i<=300;i++)
for(int j=0;j<=300;j++) timee[i][j]=1005;//初始化
pla.x=0;
pla.y=0;
pla.ttime=0;
for(int i=1;i<=m;i++)
{
int x,y,z;
x=read();
y=read();
z=read();
timee[x][y]=min(timee[x][y],z);
for(int j=1;j<=4;j++)
{
int dx=x+ed[j][1];
int dy=y+ed[j][2];
if(dx>=0&&dy>=0) timee[dx][dy]=min(timee[dx][dy],z);//记录陨石砸落的最小时间
}
}
// for(int i=0;i<=5;i++)
// {
// for(int j=0;j<=5;j++)
// cout<<time[i][j]<<" ";
// cout<<endl;
// }
bfs();
if(!flag) printf("-1");//如果未能到达安全位置则输出-1
return 0;
}
int read()
{
int x=0,f=1;
char ch=getchar();
while(ch<'0'||ch>'9'){
if(ch=='-') f=-1;
ch=getchar();
}
while(ch>='0'&&ch<='9'){
x=(x<<3)+(x<<1)+ch-'0';
ch=getchar();
}
return f*x;
}
void bfs()
{
q.push(pla);
v[0][0]=1;
while(!q.empty())
{
Node e=q.front();
q.pop();
for(int i=1;i<=4;i++)
{
int dx=e.x+ed[i][1];
int dy=e.y+ed[i][2];
if(!check(dx,dy,e.ttime+1)) continue;//判断该位置能不能走
if(v[dx][dy]) continue;
Node dd;
dd.x=dx;
dd.y=dy;
dd.ttime=e.ttime+1;
if(timee[dx][dy]==1005)//如果下个位置没有陨石则输出
{
flag=1;
printf("%d",e.ttime+1);
return ;
}
if(!d[dx][dy]) d[dx][dy]=e.ttime+1,q.push(dd),v[dx][dy]=1;
}
}
}
bool check(int x,int y,int z)//判断能不能走
{
if(x>=0&&y>=0&&z<timee[x][y]) return 1;
else return 0;
}
by __hacker__ @ 2021-10-27 02:32:35
最后一个点是超出300这个范围了,也满足要求
by 象龟迭戈 @ 2021-10-28 14:23:04
@hacker 但是我开的比300大啊,而且判断条件也没有限制300
by __hacker__ @ 2021-10-28 16:50:11
你初始化的时候就到300,应该再大一点