10.起火迷宫(简单搜索 多源BFS)

起火迷宫

↑ 题目链接

题目

一个迷宫可以看作一个 \(R\) 行 \(C\) 列的方格矩阵。
其中一些方格是空地，用 . 表示，其他方格是障碍，用 # 表示。
开始时，乔位于一块空地之中。
迷宫中一些空地已经起火了，幸运的是火还没有蔓延至乔所在的位置。
为了避免被火烧伤，乔需要尽快逃离迷宫。
已知，乔每单位时间只能沿上下左右四个方向前进一格距离，并且在前进过程中，他不能进入障碍方格。
火每单位时间都会蔓延至其上下左右四个方向的相邻空地，但是火也会被障碍阻挡。
如果一个方格已经起火或者会在乔进入方格的那一时刻恰好起火，则该方格很危险，乔不能进入。
当乔进入到任意一个位于边界的空地方格时，他都可以再花费一单位时间，直接逃离迷宫。
请问，乔想要逃离迷宫，最少需要花费的时间。

输入格式

第一行包含整数 \(T\)，表示共有 \(T\) 组测试数据。
每组数据第一行包含两个整数 \(R,C\)
接下来 \(R\) 行，包含一个 \(R×C\) 的字符矩阵。
矩阵中只包含以下四种字符：

# 表示障碍方格。
. 表示空地方格。
J 表示乔所在的空地方格，最多只有一个。
F 表示已经起火的空地方格。

输出格式

每组数据输出一行结果，一个整数表示逃离迷宫所需花费的最少时间，如果无法逃离迷宫，则输出 IMPOSSIBLE。

数据范围

\(1≤T≤10,1≤R,C≤1000\)

输入样例：

2
4 4
####
#JF#
#..#
#..#
3 3
###
#J.
#.F

输出样例：

3
IMPOSSIBLE

思路

两次 \(BFS\) 搜索，只要到达这个格子的时间严格小于这个格子被火覆盖的时间，就能走到这个格子，特判开始在边界的情况

代码

#include<bits/stdc++.h>
#define x first
#define y second
using namespace std;
const int N=1010;
typedef pair<int,int>PII;
char g[N][N];
bool st[N][N];
int df[N][N],dj[N][N];
int n,m;
int jx,jy;
int dx[]={-1,0,1,0},dy[]={0,1,0,-1};
vector<PII>fire;

//求出所有格子被火覆盖的最短时间(多源bfs, 有多个火种)
void bfs_f()
{
    
    memset(df,-1,sizeof df);
    queue<PII>q;
    
    for(auto t:fire)
    {
        q.push({t.x,t.y});
        df[t.x][t.y]=0;
    }
    
    while(q.size())
    {
        auto t=q.front();
        q.pop();
        
        for(int i=0;i<4;i++)
        {
            int a=t.x+dx[i],b=t.y+dy[i];
            if(a<0||a>=n||b<0||b>=m||g[a][b]=='#'||df[a][b]!=-1)continue;
            df[a][b]=df[t.x][t.y]+1;
            q.push({a,b});
        }
    }
   
}

//再从起点开始bfs, 只要到达这个格子的时间严格小于这个格子被火覆盖的时间，就能走到这个格子
int bfs_j()
{
    memset(dj,-1,sizeof dj);
    queue<PII>q;
    
    q.push({jx,jy});
    dj[jx][jy]=0;
    if(jx==0||jx==n-1||jx==0||jx==m-1)return 1;//一开始在边界
    while(q.size())
    {
        auto t=q.front();
        q.pop();
        
        for(int i=0;i<4;i++)
        {
            int a=t.x+dx[i],b=t.y+dy[i];
            if(a<0||a>=n||b<0||b>=m||g[a][b]=='#'||dj[a][b]!=-1||g[a][b]=='F')continue;
            if(df[a][b]!=-1&&dj[t.x][t.y]+1>=df[a][b])continue;
            dj[a][b]=dj[t.x][t.y]+1;
            if(a==0||a==n-1||b==0||b==m-1)return dj[a][b]+1;
            q.push({a,b});
        }
    }    
    
    return -1;
}

int main()
{
	int T;
	cin>>T;
	while(T--)
	{
	    fire.clear();
		cin>>n>>m;
		for(int i=0;i<n;i++)
			for(int j=0;j<m;j++)
			{
				cin>>g[i][j];
				if(g[i][j]=='J')jx=i,jy=j;
				if(g[i][j]=='F')fire.push_back({i,j});
			}
		
	    bfs_f();
	    
	    int t=bfs_j();  

	    if(t==-1)puts("IMPOSSIBLE");
	    else cout<<t<<endl;
	    
	}
	
	
	return 0;
}