uva11624：

题意：一个大火蔓延的迷宫。Joe每分钟可以走到上下左右4个方向的相邻格之一，而所有着火的格子都会往四周蔓延（即如果某个空格与着火格子有公共边，则下一分钟这个格子将会着火。）迷宫中有一些障碍，Joe和火都无法进入。当Joe走到一个迷宫的边界格子时，我们认为他已经出了迷宫。

题解：把每个着火点作为起点，做一遍BFS，得出每个格子的着火时间，然后以人的坐标为起点，做一遍BFS，此时判断条件是下一个格子的着火时间要比当前时间晚，下一个格子才可以进去。然后BFS之后，判断边界的的最小值即可。

1 #include
      
         2 #include
       
          3 #include
        
           4 #include
         
            5 #include
          
             6 #define INF 1000000000  7 using namespace std;  8 const int N=1002;  9 struct Node{ 10    int x; 11    int y; 12    int step; 13 }; 14 queue
           
            Q2; 15 int counts1[N][N]; 16 int counts2[N][N]; 17 int ct[N][N]; 18 int n,m; 19 char map[N][N]; 20 void BFS(){ 21 int dir[4][2]={ {-1,0},{ 1,0},{ 0,1},{ 0,-1}}; 22 while(!Q2.empty()){ 23 Node tp=Q2.front(); 24 Q2.pop(); 25 for(int i=0;i<4;i++){ 26 int xx=dir[i][0]+tp.x; 27 int yy=dir[i][1]+tp.y; 28 if(xx>=1&&xx<=n&&yy>=1&&yy<=m){ 29 if(map[xx][yy]!='#'&&tp.step+1
            
             Q; 48 Node temp; 49 temp.x=x; 50 temp.y=y; 51 temp.step=0; 52 Q.push(temp); 53 counts2[x][y]=0; 54 while(!Q.empty()){ 55 Node tp=Q.front(); 56 Q.pop(); 57 for(int i=0;i<4;i++){ 58 int xx=dir[i][0]+tp.x; 59 int yy=dir[i][1]+tp.y; 60 if(xx>=1&&xx<=n&&yy>=1&&yy<=m){ 61 if(tp.step+1
             
              
               >map[i][j]; 97 if(map[i][j]=='F'){ 98 Node ttp; 99 ttp.x=i;100 ttp.y=j;101 ttp.step=0;102 Q2.push(ttp);103 counts1[i][j]=0;104 }105 if(map[i][j]=='J'){106 sx=i;107 sy=j;108 }109 }110 111 BFS();112 int ans=BFS1(sx,sy);113 if(ans==INF)printf("IMPOSSIBLE\n");114 else printf("%d\n",ans+1);115 }116 }