?

题目大意：J在迷宫里工作，有一天迷宫起火了，火源有多处。每过一秒，火源都会向四个方向蔓延，J也会向四个方向移动，问J能不能跑出去，能的话输出他跑出去的最短时间，否则输出“IMPOSSIBLE”

解题思路：先进行一次BFS，找出每一点火焰蔓延到该处的最短时间。然后根据这张“火势图”，对J的行进路线进行BFS。注意J在边缘的时候，以及没有火源的时候。

#include 
   
     #include 
    
      #include 
     
       #include 
      
        #include 
       
         #include 
        
          using namespace std; const int N = 1005; typedef long long ll; int n, m; int dir[4][2] = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}}; struct Node{ int x, y, d; bool operator < (const Node& x) const { return d > x.d; } }; Node s; int cnt; int fire[N][N]; queue
         
           Q; priority_queue
          
            Q2; char map[N][N]; int BFS_F() { while (!Q.empty()) { Node p = Q.front(); Q.pop(); int px, py; for (int i = 0; i < 4; i++) { px = p.x + dir[i][0], py = p.y + dir[i][1]; if (px < 0 || py < 0 || px >= n || py >= m) continue; if (map[px][py] == '#') continue; map[px][py] = 'F'; if (fire[px][py] > p.d + 1 || fire[px][py] == -1) { fire[px][py] = p.d + 1; Q.push((Node){px, py, p.d + 1}); } } } } int BFS() { while (!Q2.empty()) { Node p = Q2.top(); Q2.pop(); for (int i = 0; i < 4; i++) { int px = p.x + dir[i][0], py = p.y + dir[i][1]; if (px < 0 || py < 0 || px >= n || py >= m) continue; if (map[px][py] == '#' || map[px][py] == 'J') continue; if (fire[px][py] >= p.d + 2) { if (px == 0 || py == 0 || px == n - 1 || py == m - 1) { return p.d + 1; } map[px][py] = 'J'; Q2.push((Node){px, py, p.d + 1}); } } } return 0; } int main() { int T; scanf(%d, &T); while (T--) { cnt = 0; memset(fire, -1, sizeof(fire)); while (!Q.empty()) Q.pop(); while (!Q2.empty()) Q2.pop(); scanf(%d %d , &n, &m); int flag = 0, flag2 = 0; for (int i = 0; i < n; i++) { for (int j = 0; j < m; j++) { scanf(%c, &map[i][j]); if (map[i][j] == 'J') { if (i == 0 || j == 0 || i == n - 1 || j == m - 1) { flag = 1; } Q2.push((Node){i, j, 0}); } else if (map[i][j] == 'F') { flag2 = 1; fire[i][j] = 0; Q.push((Node){i, j, 0}); } } getchar(); } if (!flag2) memset(fire, 0x3f, sizeof(fire)); if (flag) { printf(1 ); continue; } BFS_F(); int B = BFS(); if (!B) { printf(IMPOSSIBLE ); } else printf(%d , B + 1); } return 0; } 
          
         
        
       
      
     
    
   

?