题目

https://www.luogu.com.cn/problem/P2895#submit

思路

有一些问题与时间有关，往往题目描述是：每隔一段时间，一些点就被摧毁而不能走了，问能够到达指定点或者到达指定点的时间？

这类问题可以使用BFS求解（当然也可以使用DFS，一般使用BFS）
问题的难点在于，某一点在这一时间点可能可以走，但是下一个时间点可能就不能走了；流星摧毁的不仅是当前的点，还有相邻的点

所以我们需要求出某个点被摧毁的最早时间，在这个最早时间之前，可以走，之后便不能走了。

代码

#include<iostream>
#include<cstdio>
#include<queue>
#include<algorithm>
#define INF 0x3f3f3f3f
using namespace std;const int maxn = 300 + 10;struct node{int x,y;int step;
};
int dist[4][2] = {{0,1},{0,-1},{1,0},{-1,0}};
int a[maxn][maxn];
bool vis[maxn][maxn];
int m;
queue<node>Q;
int bfs(){node e1,e2;e1.step = e1.x = e1.y = 0;Q.push(e1);vis[0][0] = 1;while(!Q.empty()){e2 = Q.front();Q.pop();for(int i=0;i<4;i++){int xx = e2.x + dist[i][0];int yy = e2.y + dist[i][1];if(!(xx>=0 && yy>=0))continue;e1.x = xx;e1.y = yy;e1.step = e2.step + 1;if(a[xx][yy] == INF)return e1.step;//如果这个点为INF,表示永远不会被摧毁，已经安全了if(e1.step < a[xx][yy] && !vis[xx][yy]){//如果到达这个时间点的时间早于最早摧毁时间，可以走vis[xx][yy] = 1;Q.push(e1);}}}return -1;
}int main(){//初始化为INFfor(int i=0;i<maxn;i++){for(int j=0;j<maxn;j++){a[i][j] = INF;}}scanf("%d", &m);for(int i=0;i<m;i++){int x,y,t;scanf("%d %d %d", &x, &y, &t);//求出该点和周围点的最早摧毁时间a[x][y] = min(a[x][y], t);for(int j=0;j<4;j++){int xx = x + dist[j][0];int yy = y + dist[j][1];if(xx>=0 && yy>=0){a[xx][yy] = min(a[xx][yy], t);}}}printf("%d\n", bfs());return 0;
}