题目大意：

　　Bessie 为了躲避流星攻击，从原点出发每秒移动一格。流星在T时会砸到一个坐标，该坐标和周围四个格都会被破坏。问Bessie最短需花多少时间逃离到永远不会遭到袭击的地方。

　　

Input

* Line 1: A single integer: M

* Lines 2..M+1: Line i+1 contains three space-separated integers: X_i, Y_i, and T_i

Output

* Line 1: The minimum time it takes Bessie to get to a safe place or -1 if it is impossible.

Sample Input

40 0 22 1 21 1 20 3 5

Sample Output

5 用广度优先搜索，判断好条件即可

1 #include 
     
       2 #include 
      
        3 #include 
       
         4 #include 
        
          5 using namespace std; 6  7 int dir[][2] = {
   {
   0,1}, {
   0,-1},{-1,0},{
   1,0}}; 8  9 int m;10 int dtime[302][302];11 int ptime[302][302];12 13 typedef pair
         
           Point;14 queue 
          
            que;15 int main(int argc, char const *argv[])16 {17 //freopen("input.txt","r",stdin);18 scanf("%d",&m);19 for(int i = 0; i < 302; i++) {20 for(int j = 0; j < 302; j++) {21 dtime[i][j] = 1002;22 ptime[i][j] = -1;23 }24 }25 while(m--) {26 int a, b, d;27 scanf("%d %d %d",&a,&b,&d);28 dtime[a][b] = min(dtime[a][b],d);29 for(int i = 0; i < 4; i++) {30 int tx = a + dir[i][0];31 int ty = b + dir[i][1];32 if(tx >= 0 && ty >= 0 && tx < 302 && ty < 302) {33 dtime[tx][ty] = min(dtime[tx][ty], d);34 }35 }36 }37 que.push(Point(0,0));38 ptime[0][0] = 0;39 int min = 9999999;40 41 while(!que.empty()) {42 Point tp = que.front(); que.pop();43 int tpx, tpy;44 int t = ptime[tp.first][tp.second];45 if(t > min) {46 continue;47 }48 if(dtime[tp.first][tp.second] == 1002) {49 if(t < min) {50 min = t;51 }52 continue;53 }54 for(int i = 0; i < 4; i++) {55 int tpx = tp.first + dir[i][0];56 int tpy = tp.second + dir[i][1];57 if(tpx >= 0 && tpy >= 0 && tpx < 302 && tpy < 302 && ptime[tpx][tpy] == -1) {58 if(t+1 < dtime[tpx][tpy]) {59 que.push(Point(tpx, tpy));60 ptime[tpx][tpy] = t+1;61 }62 }63 }64 }65 if(min != 9999999) {66 printf("%d\n", min);67 }68 else {69 puts("-1");70 }71 return 0;72 }
          
         
        
       
      
     

做题时遇到的问题：

　　一开始没有判断使其不能回到走过的地方

　　一开始t没有加一操作，加上加一操作时的位置一开始也不对

注意到的点：

　　28行，33行min()的使用

　　注意如果无可行解要输出-1