题意：帮助joe走出一个大火蔓延的迷宫，其中joe每分钟可往上下左右四个方向之一走，所有着火的格子都会蔓延（空格与着火格有公共边，下一分钟这个空格也会着火）。迷宫中有一些障碍格，joe和火都无法进入，当joe走到一个边界的格子我们认为他走出了迷宫
输出R行C列的迷宫，#表示墙，.表示空地，J表示joe，F是着火格
如果能走出，输出最少时间否则，impossible
分析：不知道怎么处理大火蔓延这个东西，看了书上的方法，太棒了，就是对所以得着火点进行以bfs，就可以求出到蔓延到每一个格子的时间了，然后joe走的时候就看看他到这个格子的时候，时间到没到火蔓延的时候
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <queue>
using namespace std;
const int INF = 0x3f3f3f3f;
const int Max = + ;
int fire[Max][Max],g[Max][Max],vis[Max][Max];
int R,C;
int sx, sy;
int gx[] = {, , , -};
int gy[] = {-, , , };
int Time;
struct Node
{
int x,y;
};
queue<Node> Fire;
void solve(int i, int j, char ch)
{
if(ch == '#')
{
g[i][j] = -;
vis[i][j] = INF;
fire[i][j] = INF;
}
else if(ch == '.')
{
g[i][j] = ;
vis[i][j] = INF;
fire[i][j] = INF;
}
else if(ch == 'J')
{
sx = i;
sy = j;
vis[i][j] = ;
fire[i][j] = INF;
}
else if(ch == 'F')
{
fire[i][j] = ;
vis[i][j] = INF;
g[i][j] = ;
Node node;
node.x = i;
node.y = j;
Fire.push(node);
}
}
void fire_bfs() // 对大火蔓延的bfs
{
while(!Fire.empty())
{
Node node = Fire.front();
Fire.pop();
for(int i = ; i < ; i++)
{
int fx = node.x + gx[i];
int fy = node.y + gy[i];
if(fx >= && fx <= R && fy >= && fy <= C && g[fx][fy] != -)
{
if(fire[fx][fy] > fire[node.x][node.y] + )
{
fire[fx][fy] = fire[node.x][node.y] + ;
Node temp;
temp.x = fx;
temp.y = fy;
Fire.push(temp);
}
}
}
}
}
void road_bfs()
{
queue<Node> Road;
Node node;
node.x = sx;
node.y = sy;
Road.push(node);
while(!Road.empty())
{
node = Road.front();
Road.pop();
if(node.x == || node.x == R || node.y == || node.y == C)
{
Time = vis[node.x][node.y];
return;
}
for(int i = ; i < ; i++)
{
int fx = node.x + gx[i];
int fy = node.y + gy[i];
if(fx >= && fy >= && fx <= R && fy <= C && g[fx][fy] != -)
{
if(vis[fx][fy] > vis[node.x][node.y] + && vis[node.x][node.y] + < fire[fx][fy])
{
vis[fx][fy] = vis[node.x][node.y] + ;
Node temp;
temp.x = fx;
temp.y = fy;
Road.push(temp);
}
}
}
}
}
int main(int argc, char** argv)
{
int test;
scanf("%d", &test);
while (test--)
{
while(!Fire.empty())
Fire.pop();
scanf("%d%d", &R, &C);
getchar();
char ch;
for(int i = ; i <= R; i++)
{
for(int j = ; j <= C; j++)
{
scanf("%c", &ch);
solve(i, j, ch);
}
getchar();
}
Time = INF;
fire_bfs();
road_bfs();
if(Time != INF)
printf("%d\n", Time + );
else
printf("IMPOSSIBLE\n"); }
return ;
}