题目链接
题意
人要从迷宫走出去，火会向四个方向同时扩散
分析
两步bfs，先出火到达各地时的时间（设初始时间为0，人每走一步为1s，在着一步内火可以向四周可触及的方向同时扩散），然后在bfs人，人能在某地当且仅当所到时间小于火到达时间
代码
#include<iostream>
#include<queue>
#include<cstring>
#include<cstdio>
using namespace std;
const int maxn = 1000+10;
const int INF = 0x3f3f3f3f;
int R, C, tcases;
int begx, begy;
char maze[maxn][maxn];
int fire_time[maxn][maxn];
int per_time[maxn][maxn];
int vis[maxn][maxn];
int dx[] = {-1, 0, 1, 0};
int dy[] = {0, 1, 0, -1};
typedef pair<int, int> P;
queue<P> pos;
bool op(int a, int b)
{
if(a >= 0 && a < R && b >= 0 && b < C)
return true;
return false;
}
void init()
{
while(!pos.empty())
pos.pop();
memset(vis, 0, sizeof(vis));
bool is_fire = false; //看是否有火
for(int i = 0; i < R; i++)
{
for(int j = 0; j < C; j++)
{
per_time[i][j] = INF;
fire_time[i][j] = INF;
if(maze[i][j] == 'J')
{
begx = i;
begy = j;
per_time[i][j] = 0;
}
if(maze[i][j] == 'F')
{
fire_time[i][j] = 0;
vis[i][j] = 1;
is_fire = true;
pos.push(P(i, j)); //将初始时F的位置插入到队列中
}
}
}
if(!is_fire)
return ;
while(!pos.empty())
{
P p = pos.front();
pos.pop(); //该点周围已遍历，故删掉
for(int i = 0; i < 4; i++)
{
int curx = p.first + dx[i], cury = p.second + dy[i];
if(op(curx, cury) && !vis[curx][cury] && maze[curx][cury] != '#')
{
vis[curx][cury] = 1;
fire_time[curx][cury] = fire_time[p.first][p.second] + 1;
pos.push(P(curx, cury));
}
}
}
}
int bfs()
{
while(!pos.empty())
pos.pop();
memset(vis, 0, sizeof(vis));
pos.push(P(begx, begy)); //把J的初始位置插入
vis[begx][begy] = 1;
while(!pos.empty())
{
P p = pos.front();
pos.pop();
for(int i = 0; i < 4; i++)
{
int curx = p.first + dx[i], cury = p.second + dy[i];
if(!op(curx, cury))
return per_time[p.first][p.second] + 1;
if(!vis[curx][cury] && maze[curx][cury] == '.' && per_time[p.first][p.second] + 1 < fire_time[curx][cury]) //人先fire一步到达
{
vis[curx][cury] = 1;
pos.push(P(curx, cury));
per_time[curx][cury] = per_time[p.first][p.second] + 1;
}
}
}
return INF;
}
int main()
{
cin >> tcases;
//freopen("in.txt", "r", stdin);
//freopen("out.txt", "w", stdout);
while(tcases--)
{
cin >> R >> C;
for(int i = 0; i < R; i++)
scanf("%s", maze[i]);
init(); //探寻F到达各个点时的时间，用bfs
int ans = bfs();
if(ans != INF)
cout << ans << endl;
else
cout << "IMPOSSIBLE" << endl;
}
}
注意：一般 freopen("in.txt", "r", stdin）;freopen("out.txt", "w", stdout);这两句不要出现在代码里。
memset不要想当然的认为它可以对int数组赋任意值，实际上它只对-1，0有效，原因见https://blog.csdn.net/lyj2014211626/article/details/65481630， https://blog.csdn.net/ko_tin/article/details/52947059
