POJ3669 Meteor Shower

http://poj.org/problem?id=3669

类似于迷宫的一道题但是并没有给出迷宫具体什么样

但是题目已说在坐标轴的第一象限

然后障碍就是流星雨所砸范围

安全位置：永远不会发生危险的地方

那就变成一道纯广搜的题目了

具体思路：

预处理将有危险的地方标注为发生危险的时间(取最小!!!!)

其余地方取为-1(因为可能0时刻就发生危险了)

然后开始搜索

细节细节:

wrong1：超时没有放访问数组visit一个地方是不需要重复访问的不仅增加了步数搜索的时间还降低了逃生的可能性是无效操作

wrong2：将danger数组初始化为0 以为0就是安全的但是流行可以0时刻坠落

wrong3：danger赋值周围范围取最小但是在输入坠落处时忘记加判断

卡了一个晚上。。。。。

 1 #include <iostream>
 2 #include <stdio.h>
 3 #include <limits.h>
 4 #include <queue>
 5 #include <string.h>
 6 
 7 using namespace std;
 8 
 9 const int INF = INT_MAX;
10 int M,k;
11 struct Meteor
12 {
13     int x,y,t;
14 };
15 queue<Meteor> que;
16 typedef pair<int,int> P;
17 int danger[415][415];
18 bool visit[415][415];
19 int min_time = INF;
20 int d[4][2] = { {1, 0}, {0, 1}, {-1, 0}, {0, -1} };
21 
22 bool check(int x, int y)//检查是否越界 保http://poj.org/problem?id=3009证在第一象限
23 {
24     if (x < 0 || y < 0) return false;
25     return true;
26 }
27 
28 void bfs()
29 {
30     Meteor node,temp;
31     node.x = 0;
32     node.y = 0;
33     node.t = 0;
34     visit[0][0] = true;
35     que.push(node);
36     while (!que.empty())
37     {
38         node = que.front();
39         que.pop();
40         //检查是否到达安全区
41         if (danger[node.x][node.y] == -1)//如果到达安全区
42         {
43             min_time = min(min_time, node.t);
44             continue;
45         }
46         //没到安全区 那么查找周围可以走的点
47         for (int i = 0; i <4; i++)
48         {
49             if (check(node.x+d[i][0], node.y+d[i][1]))//没有越界
50             {
51                 if (visit[node.x+d[i][0]][node.y+d[i][1]]) continue;//不走重复路 否则TLE
52                 if (danger[node.x+d[i][0]][node.y+d[i][1]] == -1 || danger[node.x+d[i][0]][node.y+d[i][1]] > node.t + 1)//如果这个点可以走
53                 {
54                     temp.x = node.x + d[i][0];
55                     temp.y = node.y + d[i][1];
56                     temp.t = node.t + 1;
57                     que.push(temp);
58                     visit[temp.x][temp.y] = true;
59                 }
60             }
61         }
62     }
63 }
64 int main()
65 {
66     int tx, ty, tt;
67     freopen("in.txt", "r", stdin);
68     while (~scanf("%d", &M) )
69     {
70         min_time = INF;
71         memset(danger, -1, sizeof(danger));
72         memset(visit, false, sizeof(visit));
73         for (int i = 0; i < M; i++)
74         {
75             scanf("%d%d%d", &tx, &ty, &tt);
76             if (danger[tx][ty] < 0 || danger[tx][ty] > tt)//82行知道取最小 直接输入的时候却忘记判断了Oh !
77             danger[tx][ty] = tt;
78             for (int j = 0; j < 4; j++)
79             {
80                 if (check(tx+d[j][0],ty+d[j][1]))//如果为没有越界,周围四个点也是被摧毁的地区
81                 {
82                     danger[tx+d[j][0]][ty+d[j][1]] = danger[tx+d[j][0]][ty+d[j][1]] == -1 ? tt : min(tt, danger[tx+d[j][0]][ty+d[j][1]]);
83                 }
84             }
85         }
86         bfs();
87         if (min_time == INF)
88         printf("-1
");
89         else printf("%d
", min_time);
90     }
91     return 0;
92 }

POJ3669 Meteor Shower

相关推荐