有一个人从原点出发,然后有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; }