题意：巨大流星雨即将袭来。每个流星会对击中的地方以及周围（上下左右四格）造成破坏。Bessie开始时位于（0, 0）位置，并希望逃到一处不会被袭击到的地方（在第一象限内）。已知每移动一格需要1个时间单位，被流星破坏后的地方不能再进入。给出M个流星在T时刻击中的地方（X, Y），问Bessie能否逃到安全的地方，若能输出最短时间，否则输出-1。
思路：初始化地图，每个点初始化无穷大，再根据输入爆炸时间不断更新最早爆炸时间，然后进行宽度搜索(BFS)。
AC代码：
#include <iostream> #include <cstdio> #include<cstring> #include <iomanip> #include <algorithm> #include <cstdlib> #include <iostream> #include<queue> using namespace std; typedef pair <int,int> p; const int INF = 100000000; //输入 int n; int xx[50000], yy[50000],tt[50000]; int mg[401][401]; //保存地图 int d[401][401]; //保存最短步数 //4个方向 int dx[4] = {-1, 1, 0, 0}; int dy[4] = {0, 0, -1, 1}; void init() { //初始化地图每个点爆炸时间为无穷大 for(int i=0;i<401;i++) fill(mg[i],mg[i]+401,INF);//二维矩阵初始化方法2 //根据输入数据更改地点爆炸时间 for(int i=0;i<n;i++) { mg[xx[i]][yy[i]]=min(tt[i],mg[xx[i]][yy[i]]); } //改动上下左右最小爆照时间 for(int j=0;j<n;j++) for(int k=0;k<4;k++) { int nx=xx[j]+dx[k]; int ny=yy[j]+dy[k]; if(nx>=0&&ny>=0) mg[nx][ny]=min(tt[j],mg[nx][ny]); } //初始化走到每一点步数为无穷大 for(int i=0;i<401;i++) fill(d[i],d[i]+401,INF); } int bfs() { if(mg[0][0]==0) return -1; queue<p>que; que.push(p(0,0)); d[0][0]=0; while(!que.empty()) { p l=que.front(); int x=l.first,y=l.second; que.pop(); if(mg[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(nx>=0&&ny>=0&&d[nx][ny]==INF&&mg[nx][ny]>d[x][y]+1) { que.push(p(nx,ny)); d[nx][ny]=d[x][y]+1; } } } return -1; } void solve() { int ans=bfs(); cout<<ans<<endl; } int main() { scanf("%d",&n); for(int i=0;i<n;i++) { scanf("%d%d%d",&xx[i],&yy[i],&tt[i]); } init(); solve(); }
