J - Fire! UVA - 11624
Joe works in a maze. Unfortunately, portions of the maze have caught on fire, and the owner of the maze neglected to create a fire escape plan. Help Joe escape the maze. Given Joe’s location in the maze and which squares of the maze are on fire, you must determine whether Joe can exit the maze before the fire reaches him, and how fast he can do it. Joe and the fire each move one square per minute, vertically or horizontally (not diagonally). The fire spreads all four directions from each square that is on fire. Joe may exit the maze from any square that borders the edge of the maze. Neither Joe nor the fire may enter a square that is occupied by a wall.
Input
The first line of input contains a single integer, the number of test cases to follow. The first line of each test case contains the two integers R and C, separated by spaces, with 1 ≤ R, C ≤ 1000. The following R lines of the test case each contain one row of the maze. Each of these lines contains exactly C characters, and each of these characters is one of: • #, a wall • ., a passable square • J, Joe’s initial position in the maze, which is a passable square • F, a square that is on fire There will be exactly one J in each test case.
Output
For each test case, output a single line containing ‘IMPOSSIBLE’ if Joe cannot exit the maze before the fire reaches him, or an integer giving the earliest time Joe can safely exit the maze, in minutes.
Sample Input
2 4 4 /#### /#JF# /#…# /#…# 3 3 /### /#J. /#.F
Sample Output
3 IMPOSSIBLE
推荐阅读原文：https://blog.csdn.net/wr132/article/details/45399337
题意很简单，就是迷宫着火了，火势会蔓延，Joe要逃跑，看最后能不能逃出来，但没想到败在了英语上，大家注意，题意中用的是portions，这是一个复数形式，用词典一翻译，只看到了主体意思，没看到复数，结果就WA了20多次！！！
也就是说，Joe的起点唯一，但是起火的地方并不是唯一的，这是我们首先要明确的。
关键是之后应该怎样处理火势的蔓延与Joe逃跑这两个过程的关系，我们要清楚：只有火势可以影响Joe的逃跑路线，但Joe的逃跑路线绝对不能影响火势，所以这两个过程不可能出现在同一个BFS中。
可以这样想：既然火势的蔓延时不随人的主观意愿而改变的，那么我们可以先让火势肆意蔓延，看它到底能烧到哪里，以及烧到某个地方所需要的时间，这样，主人公在逃跑的过程中，只要在火势到达之前赶到某个地方就可以了。
综上，需要两个BFS，第一个计算火势蔓延到任意一点所需要的时间，如果火势永远到达不了某些点，就把这些点的时间设为正无穷，之后再搜索Joe的逃跑路线，条件要增加时间这一项，只要Joe能到达迷宫的边界，就算逃出来了。
代码：
#include <bits/stdc++.h> using namespace std; typedef struct node { int x,y; int step; } ty; int listt,n,m,i,j; int jx,jy; int fx[1003],fy[1003]; // 存放着火的点 int cnt; char a[1003][1003]; int via[1003][1003]; int fire[1003][1003]; // 存烧到某点需要的时间，默认是无穷大。 ty t,d; void bfs( ) { int next[4][2] = { {0,1},{0,-1},{1,0},{-1,0} }; queue <ty> Q; for ( int i=0; i<cnt; i++ ) { t.x = fx[i]; t.y = fy[i]; t.step = 0; via[t.x][t.y] = 1; Q.push(t); } while ( !Q.empty() ) { t = Q.front(); Q.pop(); fire[t.x][t.y] = t.step; // 着火时间存入数组 for ( i=0; i<4; i++ ) { d.x = t.x + next[i][0]; d.y = t.y + next[i][1]; d.step = t.step + 1; if ( d.x<0||d.y<0||d.x>=n||d.y>=m ) { continue ; } if ( a[d.x][d.y]!='#' && via[d.x][d.y]==0 ) { via[d.x][d.y] = 1; Q.push(d); } } } } int bfsr( int x, int y ) { int next[4][2] = { {0,1},{0,-1},{1,0},{-1,0} }; queue <ty> Q; t.x = x; t.y = y; t.step = 0; via[x][y] = 1; Q.push(t); while ( !Q.empty() ) { t = Q.front(); Q.pop(); if ( t.x==0 || t.x==n-1 || t.y==0 || t.y==m-1 ) { // 到达边缘即完成 return t.step ; } for ( i=0; i<4; i++ ) { d.x = t.x + next[i][0]; d.y = t.y + next[i][1]; d.step = t.step + 1; if ( d.x<0||d.y<0||d.x>=n||d.y>=m ) { continue ; } if ( a[d.x][d.y]!='#' && via[d.x][d.y]==0 && d.step<fire[d.x][d.y] ) { via[d.x][d.y] = 1; Q.push(d); } } } return -1; } int main() { cin >> listt; while ( listt-- ) { cnt = 0; cin >> n >> m; for ( i=0; i<n; i++ ) { for ( j=0; j<m; j++ ) { cin >> a[i][j]; if ( a[i][j]=='J' ) { jx = i; jy = j; } if ( a[i][j]=='F' ) { fx[cnt] = i; fy[cnt] = j; cnt ++; } } } memset(via,0,sizeof(via)); memset(fire,0x3f,sizeof(fire)); // 这个地方是正无穷啊，设成0wa了好多次 bfs(); memset(via,0,sizeof(via)); int ans = bfsr(jx,jy); if ( ans==-1 ) { cout << "IMPOSSIBLE" << endl; } else { cout << ans+1 << endl; } } return 0; }