有一个人从原点出发,然后有N个流星会在某个时刻落下,它们会破坏砸到的这个方格还会破坏
上下左右相邻的方块,输出最少多少时间之后他可以到达安全的地方,不可能则输出-1。
直接看代码更好懂
#include <bits/stdc++.h>
using namespace std;
#define ll long long
int n;
int a[1010][1010];
int sx[6] = { 0 , 0 , 0 , 0,-1, 1};
int sy[6] = { 0 , 0 , -1, 1, 0 ,0};
struct node{
int x,y,t;
};
int check(int x,int y)
{
if(x < 0 || x > 310 || y < 0 || y >310)
return 1;
return 0;
}
void bfs()
{
if(a[0][0] == 0){
cout<<"-1"<<endl;
return ;
}
if(a[0][0] == -1)
{
cout<<"0"<<endl;
return ;
}
node p,now;
queue<node> q;
p.x = p.y = p.t = 0;
q.push(p);
while(!q.empty())
{
now = q.front();
q.pop();
for(int i=2;i<=5;i++)
{
p.x = now.x + sx[i];
p.y = now.y + sy[i];
p.t = now.t + 1;
if(check(p.x,p.y))
continue;
if(a[p.x][p.y] == -1){
cout<<p.t<<endl;
return ;
}
if(p.t >= a[p.x][p.y])
continue;
a[p.x][p.y] = p.t;
q.push(p);
}
}
}
int main()
{
cin>>n;
int x,y,t;
memset(a,-1,sizeof(a));
for(int i=1;i<=n;i++)
{
cin>>x>>y>>t;
for(int j=1;j<=5;j++)
{
int tx = x+sx[j];
int ty = y+sy[j];
if(check(tx,ty))
continue;
if(a[tx][ty] == -1)
a[tx][ty] = t;
else
a[tx][ty] = min(a[tx][ty],t);
}
}
bfs();
return 0;
} 
京公网安备 11010502036488号