一起来看流星雨吧(话说我还没看到过流星雨呢)
Problem
小A则听说另一个骇人听闻的消息: 一场流星雨即将袭击整个霸中,由于流星体积过大,它们无法在撞击到地面前燃烧殆尽,届时将会对它撞到的一切东西造成毁灭性的打击。
很自然地,小A开始担心自己的安全问题。他一定要在被流星砸到前,到达一个安全的地方(也就是说,一块不会被任何流星砸到的土地)。
如果将霸中放入一个直角坐标系中,小A现在的位置是原点,并且小A不能踏上一块被流星砸过的土地。根据预报,一共有M颗流星(1 \le M \le 50,0001≤M≤50,000)会坠落在霸中上,其中第i颗流星会在时刻 T_iTi (0 \le T_i \le 1,0000≤Ti≤1,000)砸在坐标为(X_i,Y_iXi,Yi) (0 \le X_i \le 3000≤Xi≤300;0 \le Y_i \le 3000≤Yi≤300) 的格子里。
流星的力量会将它所在的格子,以及周围4个相邻的格子都化为焦土,当然小A也无法再在这些格子上行走。小A在时刻0开始行动,它只能在第一象限中, 平行于坐标轴行动,每1个时刻中,她能移动到相邻的(一般是4个)格子中的任意一个,当然目标格子要没有被烧焦才行。如果一个格子在时刻t被流星撞击或烧焦,那么小A只能在t之前的时刻在这个格子里出现。
请你计算一下,小A最少需要多少时间才能到达一个安全的格子。
注意土地的边界应该大于流星的边界,因为如果逃到那些地方也算安全地带。
Input Data
第1行: 1个正整数:MM
第2..M+2..M+1行: 第i+1i+1行为3个用空格隔开的整数:X_iXi,Y_iYi,以及T_iTi
Output Data
输出1个整数,即小A逃生所花的最少时间。如果小A无论如何都无法在流星雨中存活下来,输出-1
Input / Output Sample Input
4 0 0 2 2 1 2 1 1 2 0 3 5
Output
5
题目思路 :一道搜索题,求最小步数最好用bfs, 要记录下每个区块被摧毁的时间,具体看代码
1 #include <bits/stdc++.h> 2 using namespace std; 3 int n, t[1000][1000], inf, dx[4] = {1, 0, -1, 0}, dy[4] = {0, 1, 0, -1}, ans = 1e9; 4 bool vis[1000][1000]; 5 struct node{int xx, yy, tt;}; 6 void bfs (){ 7 queue <node> q; 8 q.push((node){1, 1, 0}); 9 while (q.size()){ 10 node tmp = q.front(); q.pop(); 11 for (int i = 0; i < 4; i++){ 12 int tx = tmp.xx + dx[i], ty = tmp.yy + dy[i]; 13 if (vis[tx][ty] or tx < 1 or tx > 302 or ty < 1 or ty > 302) continue; 14 //若越界就跳过, 注意:因为数据范围最大为300,所以上限计为302 15 if (t[tx][ty] <= tmp.tt + 1) continue; 16 if (t[tx][ty] == inf) {ans = tmp.tt + 1; return;} //t[tx][ty]为inf则是安全区 17 q.push((node){tx, ty, tmp.tt + 1}); 18 vis[tx][ty] = 1; 19 } 20 } 21 } 22 int main(){ 23 scanf ("%d", &n); 24 memset (t, 0x3f, sizeof (t)); inf = t[1][1]; //将毁坏时间初始化为最大值 25 for (int i = 1, x, y, ti; i <= n; i++){ 26 scanf ("%d %d %d", &x, &y, &ti), x++, y++; //将坐标+1后可避免越界 27 t[x][y] = min (t[x][y], ti); //当同一块被多次砸毁时时间取 min 28 for (int i = 0; i < 4; i++) t[x+dx[i]][y+dy[i]] = min (t[x+dx[i]][y+dy[i]], ti); 29 //此题对于时间的处理是关键点 30 } 31 bfs (); 32 if (ans == 1e9) ans = -1; //如果答案仍为最大值则无法走出, 计为-1; 33 printf ("%d", ans); 34 return 0; 35 }