poj3669

题意：巨大流星雨即将袭来。每个流星会对击中的地方以及周围（上下左右四格）造成破坏。Bessie开始时位于（0, 0）位置，并希望逃到一处不会被袭击到的地方（在第一象限内）。已知每移动一格需要1个时间单位，被流星破坏后的地方不能再进入。给出M个流星在T时刻击中的地方（X, Y），问Bessie能否逃到安全的地方，若能输出最短时间，否则输出-1。

分析：依旧是迷宫问题。不同的是，需要自己构建出迷宫。首先将maze的所有格初始化为INF，表示这个格子被袭击的时间为INF（即永远不会被袭击）。对于每一个流星，将其影响反映到maze上，如果破坏范围由重叠，那么格子显示的是较早的破坏时间（因为一旦破坏了就不能进入），即maze[x][y] = min(maze[x][y], T)。迷宫构建起来后，回到问题本身。求最短时间，可以用BFS做到。使用d[x]][y] 来保存移动到该格时的最小时间。而对于约束条件，就是对于下一步能否移动到该地方，要看下一个时刻该地方是否会被破坏，若不会则可以，即可d[x][y] + 1 < maze[x][y]。另外，需要特别注意的是，若有流星在0时刻袭击（0, 0）位置，则无法逃生。

注意：不要走回头路，回头就会超时。因为没必要，不重复经过肯定逼重复经过更优。

#include <iostream>
#include <queue>
#include <cstdio>
#include <algorithm>using namespace std;typedef pair<int, int> P;const int MAX_M = 500005;
const int MAX_X_Y = 405;
const int INF = 10000;int m;
int x[MAX_M], y[MAX_M], t[MAX_M];int maze[MAX_X_Y][MAX_X_Y], d[MAX_X_Y][MAX_X_Y];const int dx[4] = {-1, 1, 0, 0};
const int dy[4] = {0, 0, -1, 1};int dfs() {if(maze[0][0] == 0) return -1;queue<P> que;que.push(P(0, 0));d[0][0] = 0;while(!que.empty()) {P p = que.front();que.pop();int x = p.first;int y = p.second;if(maze[x][y] == INF) return d[x][y];for(int i=0; i<4; i++) {int nx = x + dx[i];int ny = y + dy[i];//没有超出范围、没有走过这个格子、这个格子还没有被炸 if(0<=nx && nx<MAX_X_Y && 0<=ny && ny<=MAX_X_Y && d[nx][ny]==INF && d[x][y]+1<maze[nx][ny]) {que.push(P(nx, ny));d[nx][ny] = d[x][y] + 1;}}}return -1;
}void solve() {for(int i=0; i<MAX_X_Y; i++) {fill(maze[i], maze[i]+MAX_X_Y, INF);fill(d[i], d[i]+MAX_X_Y, INF);  }for(int i=0; i<m; i++) {maze[x[i]][y[i]] = min(maze[x[i]][y[i]], t[i]);for(int j=0; j<4; j++) {int nx = x[i] + dx[j];int ny = y[i] + dy[j];if(0<=nx && nx<MAX_X_Y && 0<=ny && ny<=MAX_X_Y)maze[nx][ny] = min(maze[nx][ny], t[i]);}}printf("%d\n", dfs());
}int main() {freopen("in.txt", "r", stdin);scanf("%d", &m);for(int i=0; i<m; i++)scanf("%d %d %d", &x[i], &y[i], &t[i]);solve();fclose(stdin);return 0;
}