题意:你刚开始位于坐标轴的$(0,0)$点,一共有$m$颗流星砸向地面,每颗流星在$t$时砸到$(x,y)$点,其四周上下左右也均有波及,你每秒可以向上下左右移动一个单位,问你是否可以移动到安全的地方(没有被流星波及的点),求最小步数.

题解:这题细节有点多,但也是一个基本的bfs,首先我们要用一个数组来记录流星砸向地面的最早时间,然后还要注意你在跑到某个点的时候可能被砸中,然后搞个结构体直接bfs,当找到某个点没有被存时间的数组记录,直接输出即可.

代码:

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <stack>
#include <queue>
#include <vector>
#include <map>
#include <set>
#include <unordered_set>
#include <unordered_map>
#define ll long long
#define fi first
#define se second
#define pb push_back
#define me memset
const int N = 1e6 + 10;
const int mod = 1e9 + 7;
const int INF = 0x3f3f3f3f;
using namespace std;
typedef pair<int,int> PII;
typedef pair<ll,ll> PLL;

struct misaka{
  int x,y,t;
}p;

int dx[4]={-1,0,1,0},dy[4]={0,1,0,-1};

int m;
int x,y,t;
int jikann[400][400];
int a[400][400];

int main() {
    ios::sync_with_stdio(false);cin.tie(0);
    me(jikann,-1,sizeof(jikann));
    cin>>m;
     for(int i=1;i<=m;++i){
     	cin>>x>>y>>t;
     	if(t<jikann[x][y] || jikann[x][y]==-1){
     		jikann[x][y]=t;
     	}
     	for(int j=0;j<4;++j){
     		int tx=x+dx[j];
     		int ty=y+dy[j];
     		if(tx>=0&&ty>=0&&(t<jikann[tx][ty]||jikann[tx][ty]==-1)){
     			jikann[tx][ty]=t;
     		}
     	}
      }
     	p.x=0,p.y=0,p.t=0;
     	a[0][0]=1;
     	queue<misaka> q;
     	q.push(p);
     	while(!q.empty()){
     		misaka tmp=q.front();
     		q.pop();
     		for(int i=0;i<4;++i){
     			int tx=tmp.x+dx[i];
     			int ty=tmp.y+dy[i];
     			if(tx>=0&&ty>=0&&a[tx][ty]==0&&(tmp.t+1<jikann[tx][ty]||jikann[tx][ty]==-1)){
     				a[tx][ty]=1;
     				p.x=tx,p.y=ty,p.t=tmp.t+1;
     				q.push(p);
     				if(jikann[tx][ty]==-1){
     					cout<<p.t<<endl;
     					return 0;
     				}
     			}
     		}
     	}
        cout<<-1<<endl;
    return 0;
}