点击打开链接
题意：给出n各点的坐标及爆炸时间（每个点爆炸时都会同时殃及该点上下左右四个点），Bessie一开始在原点，求她至少走几步才能到达一个安全的位置不被炸死。
分析：此题只要注意每个点储存的是该点最早的毁灭时间即可，其他的就是普通的bfs。我这个粗心的人啊，写着写着pp就写成了p，因此半天连样例都没过，还好有美丽学长帮我找错，虽然这错让人很无语，但是还是要谢谢学长啊，以后我尽量不犯这么低级的错误。
#include<cstdio> #include<cstring> #include<algorithm> #include<iostream> #include<map> #include<vector> #include<cmath> #include<set> #include<queue> using namespace std; typedef long long ll; const int maxn = 30000 + 5; const int inf = 0x3f3f3f3f; const double eps = 0.00000000000001; int dx[] = {-1,0,0,1}; int dy[] = {0,1,-1,0}; bool judge(int x,int y) { return (x >= 0 && y >= 0); } struct point { int x,y,t; point(int x = 0, int y = 0, int t = 0):x(x), y(y),t(t){} }; int bomb[400][400]; int vis[400][400]; void bfs() { memset(vis, -1, sizeof(vis)); point p; p.x = p.y = p.t = 0; queue<point> qu; qu.push(p); vis[p.x][p.y] = 1; while(!qu.empty()) { point pp = qu.front(); qu.pop(); int x = pp.x, y = pp.y, t = pp.t; if(bomb[x][y] == inf)//找到安全的地方了 { printf("%d\n",t); return; } for(int i = 0; i < 4; i++) { int tmpx = x + dx[i]; int tmpy = y + dy[i]; int tmpt = pp.t + 1; if(judge(tmpx, tmpy) && vis[tmpx][tmpy] == -1 && tmpt < bomb[tmpx][tmpy])//在该点第一次毁灭之前经过该点是安全的，可以继续往下走 { vis[tmpx][tmpy] = 1;//标记改点走过 qu.push(point(tmpx, tmpy, tmpt)); } } } printf("-1\n");//最后别忘了找不到安全的点时也要输出 } int main() { int m; while(~scanf("%d",&m)) { // memset(bomb, -1, sizeof(bomb));//不能设初试时间为-1，而应该是inf for(int i = 0; i <= 400; i++) for(int j = 0; j <= 400; j++) bomb[i][j] = inf; int x,y,t; for(int i = 0; i < m; i++) { scanf("%d%d%d",&x,&y,&t);//每个点储存的是最早的时间 if(judge(x,y) && (bomb[x][y] == inf || bomb[x][y] > t)) bomb[x][y] = t; for(int j = 0; j < 4; j++) { int xx = x + dx[j]; int yy = y + dy[j]; if(judge(xx,yy) && (bomb[xx][yy] == inf || bomb[xx][yy] > t)) bomb[xx][yy] = t; } } bfs(); } return 0; }