2512: 【普及/提高-】【P2895】Meteor Shower S
内存限制：128 MB
时间限制：1.000 S
评测方式：文本比较
命题人：
提交：7
解决：5
题目描述
贝茜听说一场特别的流星雨即将到来：这些流星会撞向地球，并摧毁它们所撞击的任何东西。她为自己的安全感到焦虑，发誓要找到一个安全的地方（一个永远不会被流星摧毁的地方）。
如果将牧场放入一个直角坐标系中，贝茜现在的位置是原点，并且，贝茜不能踏上一块被流星砸过的土地。
根据预报，一共有 颗流星 会坠落在农场上，其中第 颗流星会在时刻 (0<=Ti<=1000)砸在坐标为 ， 的格子里。流星的力量会将它所在的格子，以及周围 个相邻的格子都化为焦土，当然贝茜也无法再在这些格子上行走。
贝茜在时刻 开始行动，它只能在第一象限中，平行于坐标轴行动，每 个时刻中，她能移动到相邻的（一般是 个）格子中的任意一个，当然目标格子要没有被烧焦才行。如果一个格子在时刻 被流星撞击或烧焦，那么贝茜只能在 之前的时刻在这个格子里出现。 贝西一开始在 。
请你计算一下，贝茜最少需要多少时间才能到达一个安全的格子。如果不可能到达输出 。
输入
共 行，第 行输入一个整数 ，接下来的 行每行输入三个整数分别为 。
输出
贝西到达安全地点所需的最短时间，如果不可能，则为 。
样例输入 复制
4
0 0 2
2 1 2
1 1 2
0 3 5样例输出 复制
5提示
#include<bits/stdc++.h>
using namespace std;
#define maxn 310
struct coord {
int x,y;
};
queue<coord> Q;
int ans[maxn][maxn],death[maxn][maxn]; //death表示该点被流星雨 砸中的时间
int wk[4][2]={{0,1},{1,0},{-1,0},{0,-1}};
int main(){
int m,Ans=100000;
memset(ans,-1,sizeof(ans)); //全部赋值为-1
memset(death,0x7f,sizeof(death)); //全部赋值为一个很大的值，大约2e10
cin>>m;
for (int i=1;i<=m;i++) {
int x,y,t;
cin>>x>>y>>t;
#define MIN(x,y,t) if (x>=0&&y>=0) death[x][y]=min(death[x][y],t)
MIN(x,y,t);
for (int k=0;k<4;k++)
MIN(x+wk[k][0],y+wk[k][1],t);
//记录下流星和上下左右影响范围烧焦的时间
}
Q.push(coord{0,0}); //原点加入到队列
ans[0][0]=0;
while(!Q.empty()) {
coord u=Q.front(); //取出队首
int ux=u.x,uy=u.y;
Q.pop();
for (int k=0;k<4;k++) { //奶牛向4个方向运动
int x=ux+wk[k][0],y=uy+wk[k][1];
if (x<0||y<0||ans[x][y]!=-1||ans[ux][uy]+1>=death[x][y])
continue; /*当目标格子的最早到达时间已经比被破坏时间晚时不能更新*/
ans[x][y]=ans[ux][uy]+1;
Q.push((coord){x,y}); //扩展的结点加入队列
}
}
for (int i=0;i<=305;i++)
for (int j=0;j<=305;j++)
if (death[i][j]>1000&&ans[i][j]!=-1)
Ans=min(Ans,ans[i][j]); /*统计答案，在所有安全区域且能达到的点中找到达最早的*/
if (Ans==100000)
puts("-1");
else
printf("%d",Ans);
return 0;
}
#include<bits/stdc++.h>
using namespace std;
struct point {
int x, y, t, step, visit;
}ps[1005][1005];
int main(){
int m, x, y, t, tx, ty, dx[5] = {-1,1,0,0,0}, dy[5] = {0,0,-1,1,0};
cin >> m;
memset(ps,-1,sizeof(ps));
for(int i = 0; i < 1000; i++) {
for(int j = 0; j < 1000; j++) {
ps[i][j].x = i;
ps[i][j].y = j;
}
}
for(int i = 0; i < m; i++) {
cin >> x >> y >> t;
for (int j = 0; j < 5; j++) {
tx = x + dx[j];
ty = y + dy[j];
if (tx < 0 || ty < 0) continue;
if (ps[tx][ty].t == -1 || ps[tx][ty].t > t ) ps[tx][ty].t = t;
}
}
queue<point> q;
ps[0][0].visit = 1;
ps[0][0].step = 0;
q.push(ps[0][0]);
while (!q.empty()) {
point p=q.front();
q.pop();
for (int i = 0; i < 4; i++) {
tx=p.x + dx[i];
ty=p.y + dy[i];
if (tx < 0 || ty < 0 || ps[tx][ty].visit == 1) continue;
if (ps[tx][ty].t == -1) {
cout << p.step + 1;
return 0;
}
if (p.step + 1 < ps[tx][ty].t) {
ps[tx][ty].visit = 1;
ps[tx][ty].step = p.step + 1;
q.push(ps[tx][ty]);
}
}
}
cout << -1;
return 0;
}