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

题意

有 $M$ 个流星即将落到地球上。其中，第 $i$ 个会在 $T_i$ 时落在 $(X_i,Y_i)$ $(0\le X_i,Y_i\le 300)$ 处，落地后，上下左右的四个格子也会被摧毁。
在第 $0$ 秒，Bessie从原点处开始移动，她在第一象限中每秒移动一个坐标格，求什么时候可以到达安全的地方。

分析

BFS，普通的BFS判断能否转移时的条件是不变的（e.g. 走迷宫时只用考虑下一步的地方通不通），但是这里判断能否转移时的条件和时间有关（流星落下前可以走，流星落下后不能走）。用 t[x][y] 表示流星落下/被旁边流星波及的最早时间，用 vis[x][y] 表示走到 $(x,y)$ 的时间。这样，在 vis[x][y] < t[x][y] 时可以走，否则不能。

安全的地方

注意到 $0\le X_i,Y_i\le 300$，所以有两种地方是安全的：

1. 在 $0\le X,Y\le 300$ 范围内，但是没有流星会落到这个格子，附近也没有流星（i.e.不会被旁边的流星波及）
2. 在 $0\le X,Y\le 300$ 范围外，一定没有流星会落在这里

其他要注意的

• t[x][y] 的初始化，特别当 $(x,y)$ 是被旁边流星波及到的时候

  1. 如果有流星在 $T$ 时落在 $(x,y)$ 处，显然 t[x][y] = min(t[x][y], T)
  2. 如果有流星在 $T$ 时落在 $(x,y)$ 附近 $(x^{\prime },y^{\prime })$ 处（$(x^{\prime },y^{\prime })$ 在 $(x,y)$ 上下左右），要注意 t[x][y] = min(t[x][y], T), 而不是 t[x][y] = min(t[x][y], t[x'][y'])。

  一开始像2这样写结果就wa了……举个反例，如果 t[x‘][y’] < T < t[x][y]，那么 t[x][y] 就会被改成 t[x'][y']，而实际上应该是 T。
  在poj评论区看到了一组数据，正确答案是13，如果得到10可能就是这里的问题。

23
2 5 10
1 3 5
5 3 12
3 3 9
1 8 7
8 4 15
2 3 7
0 0 2
6 7 10
4 4 10
3 7 7
8 5 13
0 4 9
2 6 8
0 2 4
6 4 12
0 6 7
4 2 10
1 4 7
4 6 10
5 5 12
6 5 14
2 1 2

• 不要回头
  其实正常BFS就不应该走已经走过的路，但是不知道为什么一开始觉得这题可以回头走，结果TLE了，应该是死循环了……

代码

#include<iostream>
#include<cstring>
#include<queue>
using namespace std;const int maxn = 305;
int t[maxn][maxn], vis[maxn][maxn];const int dx[4] = {0, 0, 1, -1};
const int dy[4] = {1, -1, 0, 0};struct point	{	int x, y;	};bool range(point p)
{return p.x >= 0 && p.x < maxn && p.y >= 0 && p.y < maxn;
}int main()
{memset(vis, -1, sizeof(vis));for(int i = 0; i < maxn; i ++)for(int j = 0; j < maxn; j ++)t[i][j] = 1005;int m;	scanf("%d", &m);for(int i = 0; i < m; i ++){int xm, ym;int tmp;scanf("%d%d%d", &xm, &ym, &tmp);t[xm][ym] = min(t[xm][ym], tmp);for(int j = 0; j < 4; j ++){point nxt;nxt.x = xm + dx[j];	nxt.y = ym + dy[j];if(!range(nxt))	continue;t[nxt.x][nxt.y] = min(tmp, t[nxt.x][nxt.y]);}}queue<point> q;while(!q.empty())	q.pop();point tmp;tmp.x = tmp.y = 0;q.push(tmp);vis[0][0] = 0;int ans = -1;while(!q.empty()){tmp = q.front();	q.pop();if(t[tmp.x][tmp.y] > 1000){ans = vis[tmp.x][tmp.y];break;}point nxt;for(int i = 0; i < 4; i ++){nxt.x = tmp.x + dx[i];nxt.y = tmp.y + dy[i];if(!range(nxt))	continue;if(vis[tmp.x][tmp.y] + 1 >= t[nxt.x][nxt.y])continue;else{vis[nxt.x][nxt.y] = vis[tmp.x][tmp.y] + 1;q.push(nxt);}}}printf("%d\n", ans);return 0;
}