$$\color{Purple}{kuangbin题解目录}$$
描述
一个迷宫可以看作一个 $R$ 行 $C$ 列的方格矩阵。
其中一些方格是空地,用 .
表示,其他方格是障碍,用 #
表示。
开始时,乔位于一块空地之中。
迷宫中一些空地已经起火了,幸运的是火还没有蔓延至乔所在的位置。
为了避免被火烧伤,乔需要尽快逃离迷宫。
已知,乔每单位时间只能沿上下左右四个方向前进一格距离,并且在前进过程中,他不能进入障碍方格。
火每单位时间都会蔓延至其上下左右四个方向的相邻空地,但是火也会被障碍阻挡。
如果一个方格已经起火或者会在乔进入方格的那一时刻恰好起火,则该方格很危险,乔不能进入。
当乔进入到任意一个位于边界的空地方格时,他都可以再花费一单位时间,直接逃离迷宫。
请问,乔想要逃离迷宫,最少需要花费的时间。
输入格式
第一行包含整数 $T$,表示共有 $T$ 组测试数据。
每组数据第一行包含两个整数 $R,C$。
接下来 $R$ 行,包含一个 $R \\times C$ 的字符矩阵。
矩阵中只包含以下四种字符:
#
表示障碍方格。.
表示空地方格。J
表示乔所在的空地方格,最多只有一个。F
表示已经起火的空地方格。
输出格式
每组数据输出一行结果,一个整数表示逃离迷宫所需花费的最少时间,如果无法逃离迷宫,则输出 IMPOSSIBLE
。
数据范围
$1 \\le T \\le 10$,
$1 \\le R,C \\le 1000$。
输入样例:
2
4 4
####
#JF#
#..#
#..#
3 3
###
#J.
#.F
输出样例:
3
IMPOSSIBLE
思路
基于bfs思想,先把火的蔓延情况跑一遍$bfs$,然后把人(注意考虑他到达边界的情况和他能走的情况必然在火蔓延之前,即$t_{人}+1 < t_{火}$)的行走情况跑一遍$bfs$.
代码
#include <iostream>
#include <cstring>
#include <algorithm>
#include <queue>
#include <vector>
#define MAXN 1010
using namespace std;
const int inf=0x3f3f3f3f;
typedef pair<int, int> PII;
int dir[4][2]={{0,-1},{1,0},{0,1},{-1,0}};
int t,n,m,sx,sy;
char g[MAXN][MAXN];
int dist[MAXN][MAXN];//火
int Dist[MAXN][MAXN];//人
vector<PII> v;
int bfs()
{
queue<PII> q;
for(int i=0;i<v.size();i++)
{
q.push({v[i].first,v[i].second});
dist[v[i].first][v[i].second]=0;
}
while(q.size()>0)
{
PII temp=q.front();
q.pop();
for(int i=0;i<=3;i++)
{
int dx=temp.first+dir[i][0],dy=temp.second+dir[i][1];
if(dx>=1&&dx<=n&&dy>=1&&dy<=m&&dist[dx][dy]==inf&&g[dx][dy]=='.')
{
dist[dx][dy]=dist[temp.first][temp.second]+1;
q.push({dx,dy});
}
}
}
}
int BFS()
{
if(sx==1||sx==n||sy==1||sy==m)
return 1;
queue<PII> q;
q.push({sx,sy});
Dist[sx][sy]=0;
while(q.size()>0)
{
PII temp=q.front();
q.pop();
if(temp.first==1||temp.first==n||temp.second==1||temp.second==m)
return Dist[temp.first][temp.second]+1;
for(int i=0;i<=3;i++)
{
int dx=temp.first+dir[i][0],dy=temp.second+dir[i][1];
if(dx>=1&&dx<=n&&dy>=1&&dy<=m&&Dist[dx][dy]==inf&&g[dx][dy]=='.'&&Dist[temp.first][temp.second]+1<dist[dx][dy])
{
Dist[dx][dy]=Dist[temp.first][temp.second]+1;
q.push({dx,dy});
}
}
}
return 0;
}
int main()
{
cin >> t;
while(t--)
{
memset(dist,0x3f,sizeof(dist));
memset(Dist,0x3f,sizeof(Dist));
v.clear();
cin >> n >> m;
for(int i=1;i<=n;i++)
{
cin >> g[i]+1;
for(int j=1;j<=m;j++)
{
if(g[i][j]=='J')
sx=i,sy=j;
else if(g[i][j]=='F')
v.push_back({i,j});
}
}
bfs();//火
int res=BFS();
if(res!=0)
cout << res << endl;
else cout << "IMPOSSIBLE" << endl;
}
return 0;
}