-->Fire!
直接上中文
Descriptions:
乔在迷宫中工作。不幸的是，迷宫的一部分着火了，迷宫的主人没有制定火灾的逃跑计划。请帮
助乔逃离迷宫。根据乔在迷宫中的位置以及迷宫的哪个方块着火，你必须确定火焰烧到他之前，
乔是否可以离开迷宫，如果能离开他能跑多快。
乔和火每分钟移动一个方格，上、下、左、右，四个方向中的一个。火势向四个方向同时蔓延。
乔可以从迷宫的任何一个边界逃离迷宫。无论是乔还是火都不会到达有墙的位置。
输入
第一行输入包含一个整数，即测试次数
每个测试用例的第一行包含两个
整数R和C，用空格分隔，1≤R，C≤1000
下面R行中，每一行都包含C个字符，以及每个字符是以下之一：
# 代表墙
. 代表空地，火和乔是可通行的
J 乔在迷宫中最初的位置，火和乔是可通行的
F 代表火
在每组测试中只有一个J
输出
对于每个测试用例，如果在火蔓延的时候烧到了乔，则乔无法逃出迷宫，输出'IMPOSSIBLE'
如果乔能逃出迷宫，则输出乔最快可以在几分钟内安全逃出迷宫，每组输出占一行
样例输入
样例输出
题目链接：
https://vjudge.net/problem/UVA-11624
注意火不止一个，火是固定的且火走过的地方时间也是一样的，所以可以先把火走的地方需要的时间处理一下，然后再对人bfs，多加一个条件，人在这个地方的时间要小于火在这个地方的时间
AC代码
#include <iostream>
#include <cstdio>
#include <fstream>
#include <algorithm>
#include <cmath>
#include <deque>
#include <vector>
#include <queue>
#include <string>
#include <cstring>
#include <map>
#include <stack>
#include <set>
#include <sstream>
#define mod 1000000007
#define eps 1e-6
#define ll long long
#define INF 0x3f3f3f3f
#define MEM(x,y) memset(x,y,sizeof(x))
using namespace std;
int T,n,m;
char mp[][];//原始地图
int visfire[][];//记录火是否烧过
int vispeople[][];//记录人是否走过
int firetime[][];//火经过这个地方的时间
int peopletime[][];//人经过这个地方的时间
int dt[][]= {{,},{-,},{,},{,-}};//四个方向
struct node
{
int x,y;//坐标
};
node now,net;
queue<node>fire;//两个队列 火和人
queue<node>people;
void judgetime()//预处理火经过的地方的时间
{
while(!fire.empty())
{
now=fire.front();
fire.pop();
for(int i=; i<; i++)//四种走法
{
int tx=now.x+dt[i][];
int ty=now.y+dt[i][];
if(tx>=&&tx<n&&ty>=&&ty<m&&!visfire[tx][ty]&&mp[tx][ty]!='#')
{
net.x=tx;
net.y=ty;
visfire[tx][ty]=;//标记已烧过
fire.push(net);//入队
firetime[tx][ty]=firetime[now.x][now.y]+;//时间加1
}
}
}
}
void bfs()//人
{
int f=;
while(!people.empty())
{
now=people.front();
people.pop();
if(now.x<=||now.x>=n-||now.y<=||now.y>=m-)//人走出来了
{
f=;
cout<<peopletime[now.x][now.y]+<<endl;
break;
}
for(int i=; i<; i++)//四种走法
{
net.x=now.x+dt[i][];
net.y=now.y+dt[i][];
if(net.x>=&&net.x<n&&net.y>=&&net.y<m&&!vispeople[net.x][net.y]&&mp[net.x][net.y]=='.'&&peopletime[now.x][now.y]+<firetime[net.x][net.y])
{
vispeople[net.x][net.y]=;//标记已走过
people.push(net);//入队
peopletime[net.x][net.y]=peopletime[now.x][now.y]+;//时间+1
}
}
}
if(f==)
cout<<"IMPOSSIBLE"<<endl;
}
int main()
{
cin>>T;
while(T--)
{
MEM(firetime,INF);//初始化
MEM(peopletime,INF);
MEM(visfire,);
MEM(vispeople,);
cin>>n>>m;
for(int i=; i<n; i++)
{
for(int j=; j<m; j++)
{
cin>>mp[i][j];
if(mp[i][j]=='J')
{
now.x=i;
now.y=j;
vispeople[i][j]=;
people.push(now);
peopletime[i][j]=;
}
if(mp[i][j]=='F')
{
now.x=i;
now.y=j;
visfire[i][j]=;
fire.push(now);
firetime[i][j]=;
}
}
}
judgetime();
// for(int i=0; i<n; i++)
// {
// for(int j=0; j<m; j++)
// {
// cout<<firetime[i][j]<<" ";
// }
// cout<<endl;
// }
bfs();
while(!fire.empty())//清空队列
{
fire.pop();
}
while(!people.empty())
{
people.pop();
}
}
}