一、题意：流星雨来袭击我们的女主，Bessie。为了找一个安全地方，她开始逃了。地图相当于平面坐标系第一象限，Bessie一开始在原点。然后，每颗流星都会在某个时刻砸下来，砸到的地方连同上下左右都会被毁灭，此时这些地方Bessie就不能通过了，她只能走其它地方。Bessie的移动速度是每时刻移动一步，上下左右，不能对角线移动。现在求Bessie最小的移动步数。

 

二、思路：先将会被毁灭的坐标点标记上被毁灭的时间，然后bfs，当到达该坐标的步数小于被毁灭的时间时可走，直到找到第一个不会被毁灭的坐标为止。这里需要注意的一个点就是当时间Ti==0时的情况。

 

三、代码：

#include"iostream"#include"stdio.h"#include"string.h"#include"queue"using namespace std;typedef pair
     
       P;const int MAXN=305;int coordinate[MAXN][MAXN];int dist[MAXN][MAXN];void CoordinateChange(int x,int y,int time){    if(coordinate[x][y]>time||coordinate[x][y]==-1)        coordinate[x][y]=time;    int dx[4]={0,1,0,-1};    int dy[4]={1,0,-1,0};    for(int i=0;i<4;i++)    {        int nx=x+dx[i];        int ny=y+dy[i];        if(nx>=0&&ny>=0)            if(coordinate[nx][ny]>time||coordinate[nx][ny]==-1)                coordinate[nx][ny]=time;    }}bool Judge(int x,int y,int d){    if(x>=0&&y>=0&&(coordinate[x][y]==-1||d
      
        que;    que.push(P(0,0));    while(que.size())    {        P p=que.front();que.pop();        if(coordinate[p.first][p.second]==-1)            return dist[p.first][p.second];        int dx[4]={0,1,0,-1};        int dy[4]={1,0,-1,0};        for(int i=0;i<4;i++)        {            int nx=p.first+dx[i];            int ny=p.second+dy[i];            if(Judge(nx,ny,dist[p.first][p.second]+1))            {                dist[nx][ny]=dist[p.first][p.second]+1;                que.push(P(nx,ny));            }        }    }    return -1;}int main(){  //  freopen("in.txt","r",stdin);    int m,x,y,time;    while(scanf("%d",&m)==1)    {        memset(coordinate,-1,sizeof(coordinate));        memset(dist,-1,sizeof(dist));        for(int i=0;i
       
        >x>>y>>time;            CoordinateChange(x,y,time);        }        /*        for(int i=0;i<10;i++)        {            for(int j=0;j<10;j++)                cout<
        
         <<' ';            cout<