BFS - Meteor Shower - 流星雨

题解这个是我前三个月扔下的题，原来一直没有读懂是什么意思ps：这次也是看了别人的博客才知道大意：给你M个坐标，坐标后面是这个点爆炸的时间，注意点爆炸以后就不能再去了，不是只是一瞬间。 从源点开始，找一个永远都不会爆炸的点 所需要的时间（步数）题解：说了x,y的范围是小于300，所以这个矩阵就是一个300行列的矩阵。注意：输入的不是矩阵！！！(我一直以为是，所以才没看懂)矩阵初始值为inf（极大的数），哦对，这个矩阵不是真的，是一个存放每个点的爆炸时间在输入的过程中，每次都刷新原来的矩阵爆炸时间，因为爆炸完就不能用了，所以每次矩阵取最小的爆炸时间然后利用BFS进行搜索(因为是最短时间) #include <iostream> #include <algorithm> #include <queue> #include <stdio.h> using namespace std; const int MAX = 305; // 初始流行掉落的时间 int inf = 1 << 30; int dp[MAX][MAX]; // 控制方向 int dx[] = {0, 1, 0, -1, 0}; int dy[] = {1, 0, -1, 0, 0}; struct node { int x, y, t; }; int BFS() { queue<node> q; // 可能(0,0) 点爆炸时间是0 if (dp[0][0] > 0) q.push((node){0, 0, 0}); while (!q.empty()) { node t = q.front(); q.pop(); // 如果发现了一个可以不被爆炸的地方 if (dp[t.x][t.y] == inf) return t.t; // 扫描临点 for (int i = 0; i < 4; i++) { int nx = t.x + dx[i]; int ny = t.y + dy[i]; // t.t+1 是因为走过去也得花时间 // t.t是当前已经花的时间 if (nx >= 0 && ny >= 0 && t.t + 1 < dp[nx][ny]) { // 防止在回去 if (dp[nx][ny] != inf) dp[nx][ny] = t.t + 1; q.push((node){nx, ny, t.t + 1}); } } } return -1; } int main() { int N; cin >> N; // 这才知道原来二维的也能用fill fill(dp[0], dp[0] + MAX * MAX, inf); while (N--) { int x, y, t; scanf("%d%d%d", &x, &y, &t); // 修改与他相邻的点的爆炸时间 for (int i = 0; i < 5; i++) { int nx = x + dx[i]; int ny = y + dy[i]; // 等于最小的爆炸时间 if (nx >= 0 && ny >= 0) { dp[nx][ny] = min(dp[nx][ny], t); } } } cout << BFS(); return 0; }