poj 3669 Meteor Shower bfs

缘起

日常水题 poj 3669 Meteor Shower

分析

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
就是给你一个第一象限，你从(0,0)出发在第一象限移动. 但是给你M颗流星. 这颗流星(xi,yi,ti)表示这颗流星
在ti时刻将袭击(xi,yi), 而且将摧毁(xi,yi)相邻的四个格点. 自ti起，被流星摧毁的格点将再也无法前往了.
那么要求你计算逃生的最短时间.

【输入】
第一行是M (1 ≤ M ≤ 50000)
然后M行是 (xi,yi,ti)
(0 ≤ Xi ≤ 300; 0 ≤ Yi ≤ 300) at time Ti (0 ≤ Ti  ≤ 1,000)

【输出】
最短时间或者-1（表示根本不可能逃生）

【样例输入】
4
0 0 2
2 1 2
1 1 2
0 3 5

【样例输出】
5

【限制】
Time limit 1000 ms 
Memory limit 65536 kB

【来源】
USACO 2008 February Silver

状态转移过程中要考虑两件事情. 第一件事情是能不能去（有木有被摧毁）. 第二件事情是安不安全（即能不能久留）. bfs过程中第一个可以久留的点就是安全区域.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
//#include "stdafx.h"

#include <stdio.h>
#include <string.h>
#include <queue>
//#define LOCAL
using namespace std;
int n, map[305][305], dir[5][2]={{0,0},{1,0},{-1,0},{0,1},{0,-1}}; // map[i][j]表示最早遭受袭击的时间（包括溅射伤害）
typedef pair<int,int> P;
bool v[305][305];

struct Node // 时间t到达p
{
	P p;
	int t;
	Node(P p, int t):p(p),t(t){}
};

bool safe(Node node) // 点p是否永久安全?
{
	return map[node.p.first][node.p.second] == 0x3f3f3f3f;
}

bool ok(int i, int j, int t) // 时间t到达(i,j)是否安全?
{
	return !v[i][j]&&i>=0 && j>=0 && map[i][j]>t;
}

int bfs()
{
	queue<Node> q;
	q.push(Node(P(0,0),0));
	v[0][0] = true;
	while(!q.empty())
	{
		Node front = q.front(); // front是已经到达的格点
		q.pop();
		if (safe(front)) // 如果永久安全
		{
			return front.t;
		}
		// 说明front不是永久安全, 需要转移
		for (int i = 1,nx,ny; i<=4; i++)
		{
			nx = front.p.first+dir[i][0], ny = front.p.second+dir[i][1];
			if (ok(nx,ny, front.t+1))
			{
				v[nx][ny] = true;
				q.push(Node(P(nx, ny), front.t+1));
			}
		}
	}
	return -1; // 要是能返回肯定早返回了
}

int main()
{
#ifdef LOCAL
	freopen("d:\\data.in", "r", stdin);
	//freopen("d:\\my.out", "w", stdout);
#endif
	scanf("%d", &n);
	memset(map, 0x3f, sizeof(map));
	while(n--)
	{
		int x,y,t;
		scanf("%d%d%d", &x, &y, &t);
		for (int i = 0,nx,ny; i<=4;i++)
		{
			nx = x+dir[i][0];
			ny = y+dir[i][1];
			if (nx>=0 && ny>=0 && map[nx][ny]>t)
			{
				map[nx][ny] = t;
			}
		} // 得到map上每个点最早遇袭时间
	}
	printf("%d\n", bfs());
	return 0;
}

ac情况

Status Accepted
Time 125ms
Memory 556kB
Length 1426
Lang C++
Submitted 2019-08-23 16:19:27
Shared
RemoteRunId 20792255