题目描述：

        题意是在某一时刻t会有一个陨石落下来，会落到坐标为x，y的地方，陨石落下来之后不但x，y会遭到破坏，和x，y四邻接的点也会被破坏。现在Bessie的初始位置在原点，每一个单位时间只能平行于坐标轴，移动一个单位距离，题目要求需要几个单位时间Bessie才能移动到安全的地方（只能运动在坐标轴和第一象限）。由于陨石落下来之前，某个点还是可以走的，直到t时刻陨石落下来破坏掉该点。

 

        明确题意后首先想到的是BFS，预处理是这题的难点，由于某个点遭到破坏后就不能走了，因此如果有多次遭破坏只要记录改点遭破坏的最早的时间就可以了。bfs的时候如果移动步数大于等于该点被破坏的时间，那么该节点就不能被扩展。直到走到不会被陨石破坏的点为止。

 

代码如下：

        数组mp记录了每个点被陨石破坏的最早时间，如果不会被破坏则用-1表示（由于题目中t可以是0，因此不能用0表示不会被破坏，在这里wa了一次）

 

#include 
    
     #include 
     
      #include 
      
       #include 
       
        using namespace std;int mp[309][309];int dir[4][2] = {
   {1,0}, {-1,0}, {0,-1}, {0,1}};int visit[309][309];struct State{	int x, y, step;	State(int x, int y, int step) : x(x), y(y), step(step) {}};bool inFirstQuadrant( int x, int y ){	if ( x >= 0 && y >= 0 ) return true;	return false;}void setPoint(int x, int y, int t){	if ( mp[x][y] == -1 ) mp[x][y] = t;	else mp[x][y] = min(mp[x][y], t);}void destroyPoint( int x, int y, int t ){	setPoint(x, y, t);	for ( int i=0; i<4; i++ )	{		int tx = x + dir[i][0];		int ty = y + dir[i][1];		if ( inFirstQuadrant( tx, ty ) ) 			setPoint( tx, ty, t );	}}void BFS(){	State origin( 0, 0, 0 );	queue
        
          Q;	Q.push( origin );	visit[0][0] = 1;	while( ! Q.empty() )	{		State cur = Q.front();		Q.pop();		if ( mp[cur.x][cur.y] == -1 )		{			cout << cur.step << endl;			return;		}		for ( int i=0; i<4; i++ )		{			int x = cur.x + dir[i][0];			int y = cur.y + dir[i][1];			if ( inFirstQuadrant(x, y) && !visit[x][y])			{				if ( cur.step + 1 < mp[x][y] || mp[x][y] == -1)				{					State p( x, y, cur.step + 1 );					Q.push( p );					visit[x][y] = 1;				}			}		}	}	cout << -1 << endl;}int main(){	int m;	while ( cin >> m )	{		memset( mp, -1, sizeof(mp) );		memset( visit, 0, sizeof(visit) );		int x, y, t;		for ( int i=0; i
         
          > x >> y >> t; destroyPoint( x, y, t ); } BFS(); } return 0;}