POJ 3669 Meteor Shower
https://vjudge.net/problem/POJ-3669
题意
有一场流星雨即将到来，Bessie要找到一个安全的地方。现在已知有M颗流星，并且知道它们抵达的位置和时间，Bessi走一个单位需要一个单位时间，问到达安全位置的最短时间，如果无法到达安全位置就输出-1。
细则：
1、Bessie从起点出发，可以向上下左右四个方向行走。
2、流星会摧毁自己所在点以及该点上下左右的点。
3、在流星刚好到达或者被流星摧毁过的位置都是不可到达的。
Sample Input
4
0 0 2
2 1 2
1 1 2
0 3 5
Sample Output
5
思路：其实就是一个求最短路的问题，只是因为终点无法固定下来用最短时间来替代，所以用BFS从起点在身边搜，搜到安全的位置就停止就好了。
#include<iostream>
#include<cstring>
#include<queue>using namespace std;const int INF = 0x3f3f3f3f;
const int Maxn = 300 + 10;
typedef struct {int x,y,t; //分别是流星到达的坐标和时间
}node;
node now, next;//当前点以及即将抵达的点
int mp[Maxn][Maxn];
int dir[][2]= {{1,0},{-1,0},{0,1},{0,-1},{0,0}};//多了一个(0,0)，因为流星会摧毁所在点int bfs() {if(mp[0][0] == -1)return 0;//如果起点安全就直接返回if(mp[0][0] == 0)return -1;//如果直接被流星砸到，返回-1queue <node> que;now.x = 0;now.y = 0;now.t = 0;//原点que.push(now);while(!que.empty()) {now = que.front();que.pop();for(int i = 0; i < 4; i++) {next.x = now.x + dir[i][0];next.y = now.y + dir[i][1];next.t = now.t + 1; //一步一秒if(next.x < 0 || next.y < 0)continue;//出界if(mp[next.x][next.y] == -1)//找到安全位置return next.t;if(next.t >= mp[next.x][next.y])//该点已被摧毁continue;mp[next.x][next.y] = next.t;//防止再次走到这个点que.push(next);}}return -1;
}
int main() {memset(mp, -1, sizeof(mp));//mp初始化为-1int m;cin >> m; int xi, yi, ti;for(int i = 0; i < m; i++) {cin >> xi >> yi >> ti;for(int j = 0; j < 5; j++) { //记录被摧毁时间int nx = xi + dir[j][0];int ny = yi + dir[j][1];if(nx < 0 || nx > 300 || ny < 0 || ny > 300)continue;if(mp[nx][ny] == -1)//未被摧毁直接赋值mp[nx][ny] = ti;else //被摧毁过记录最早时间mp[nx][ny] = min(mp[nx][ny], ti);}}cout << bfs() << endl;return 0;
}
