题目描述

乔在迷宫中工作。不幸的是，迷宫的一部分着火了，迷宫的主人没有制定火灾的逃跑计划。请帮助乔逃离迷宫。根据乔在迷宫中的位置以及迷宫的哪个方块着火，你必须确定火焰烧到他之前，乔是否可以离开迷宫，如果能离开他能跑多快。
乔和火每分钟移动一个方格，上、下、左、右，四个方向中的一个。火势向四个方向同时蔓延。乔可以从迷宫的任何一个边界逃离迷宫。无论是乔还是火都不会到达有墙的位置。

输入

第一行输入包含一个整数，即测试次数
每个测试用例的第一行包含两个
整数R和C，用空格分隔，1≤R，C≤1000
下面R行中，每一行都包含C个字符，以及每个字符是以下之一：
# 代表墙
. 代表空地，火和乔是可通行的
J 乔在迷宫中最初的位置，火和乔是可通行的
F 代表火
在每组测试中只有一个J

输出

对于每个测试用例，如果在火蔓延的时候烧到了乔，则乔无法逃出迷宫，输出'IMPOSSIBLE'如果乔能逃出迷宫，则输出乔最快可以在几分钟内安全逃出迷宫，每组输出占一行

样例输入

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

样例输出

3
IMPOSSIBLE

 

思路分析：这道题的关键就在于两个东西会同时移动，无法判断，所以我们想办法让他们同时移动。

以下有两个思路：

(1)：两个同时进行BFS，边走边更新，但是这时有一个问题就是 样例中的 第二个 ，J是跑不出去的，为什么？他走到哪个边都会被下一步的火给烧掉，但是如果先更新 J 的路径 ，第二个样例是过不了的。所以我们先让火走，火更新与火相邻的点，然后人在走，只需要每次都看一下前面是不是火或者是不是#（不能走）就可以了。注意一些细节：

1.火可以走人走过的，不可以走火走过的(因为这样会复杂度变高)，而人不能走人走过的也不能走火走过，而且两者都不能走#。

2.火在走人走过的路径之后，这个路径可以继续被火更新。

3.当人到达任意一个边界，因为是火先走的，说明火在没有封到这个边界的情况下，人已经到达了说明可以出去。

直接代码+注释：

#include <queue>
#include <cstdio>
#include <stdlib.h>
#include <string.h>
#include <math.h>
#include <iostream>
#include <stack>
#include <algorithm>
#include <vector>
#define MIN(x,y) ((x)<(y)?(x) : (y))
#define MAX(x,y) ((x)>(y)?(x) : (y))
using namespace std;
typedef long long ll;
const int mod=10007;
const int INF=0x7fffffff;
const int maxn=1e6+5;
bool vis[2][1005][1005];//0 1 代表 火的路径 和 人的路径
struct node{
    int x,y,step=0;
    bool judge;//用judge判断以下是人还是火
}F[1000],Qiao;//存取多个火的起点与一个人的起点
int m,n,cnt=0;//m是行
char str[1005][1005];
int dx[5]={0,0,1,-1};
int dy[5]={-1,1,0,0};
bool check(int x,int y)
{
    if(x<1||y<1||x>m||y>n)//判界一定要判正确
        return false;
    return true;
}
int bfs()
{
    queue<node>q;
    for(int i=1;i<=cnt;i++)
    {
        q.push(F[i]);
        vis[1][F[i].x][F[i].y]=true;
    }//让火先走 
    q.push(Qiao); vis[0][Qiao.x][Qiao.y]=true;
    while(!q.empty())
    {
        node now=q.front();q.pop();
        if(now.judge==false&&(now.x==1||now.y==1||now.x==m||now.y==n))
            return now.step+1;//人到达任意边就可以
        for(int i=0;i<4;i++)
        {
            node N;
            N.x=now.x+dx[i];N.y=now.y+dy[i];
            if(now.judge==false)
            {
                if(check(N.x,N.y)&&str[N.x][N.y]=='.'&&vis[0][N.x][N.y]==false&&vis[1][N.x][N.y]==false)
                {
                    N.judge=now.judge;
                    N.step=now.step+1;
                    q.push(N);
                    vis[0][N.x][N.y]=true;
                }
            }
            else
            {
                if(check(N.x,N.y)&&vis[1][N.x][N.y]==false&&str[N.x][N.y]=='.')
                {
                    N.judge=now.judge;//火会更新人走过的路径并且让人走过的路径也变成火
                    q.push(N);
                    vis[1][N.x][N.y]=true;
                }
            }
        }
    }
    return -1;
}
int main()
{
    int T;
    scanf("%d",&T);
    while(T--)
    {
        cnt=0;//多组输入！！！我刚开始死在这了！！
        memset(str,0,sizeof(str));
        memset(vis,false,sizeof(vis));//初始化别忘记
        scanf("%d%d",&m,&n);
        for(int i=1;i<=m;i++)
            scanf("%s",str[i]+1);
        for(int i=1;i<=m;i++)
            for(int k=1;k<=n;k++)
            {
                if(str[i][k]=='F')
                 {
                     F[++cnt].x=i;F[cnt].y=k;
                     F[cnt].judge=true; 
                     F[cnt].step=0;
                 }
                if(str[i][k]=='J')
                {
                    Qiao.x=i;Qiao.y=k;
                    Qiao.step=0;Qiao.judge=false;
                }
            }
        int ans=bfs();
        if(ans==-1) printf("IMPOSSIBLE\n");
        else printf("%d\n",ans);
    }
    return 0;
}

然后接下来介绍另一种思路：

我们既然可以的思路是让他同时移动，所以我们可以让一个先走记录到一个点的最短时间，判断令一个走到这的时候时间大于还是小于。比如，我们让火先走BFS，去更新他扩散到每一个点的最短时间，然后我们让这个人开始跑，这个人跑到可以跑到一个点的前提是，火扩散到这个点的时间要大于人走到这的时间，这个点就可以继续走，当到边界时还需要判定以下 时间差，如果小于 火到这的最短时间，那么就出去就好了，当然这个思路也有几个细节：

1.初始化一定不能忘。

2.注意每一次都要判断以下这个点可不可以走，即要小于火到这的最短时间。

3.判断边界。

直接代码+注释：

#include <queue>
#include <cstdio>
#include <stdlib.h>
#include <string.h>
#include <math.h>
#include <iostream>
#include <stack>
#include <algorithm>
#include <vector>
#define MIN(x,y) ((x)<(y)?(x) : (y))
#define MAX(x,y) ((x)>(y)?(x) : (y))
using namespace std;
typedef long long ll;
const int mod=10007;
const int INF=0x3f3f3f3f;
const int maxn=1e6+5;
struct node{
    int x,y,step=0;
}F[1000],Qiao;
int m,n,cnt=0;//m是行
int num[1005][1005];//记录火更新扩散的时间
char str[1005][1005];//地图
int dx[5]={0,0,1,-1};
int dy[5]={-1,1,0,0};
bool vis[1005][1005];//标记人走过的路径
int bfs()
{
    queue<node>q;
    while(!q.empty()) q.pop();
    q.push(Qiao);
    vis[Qiao.x][Qiao.y]=true;//不要忘记标记
    while(!q.empty())
    {
        node pre=q.front();q.pop();
        if(pre.x==1||pre.y==1||pre.x==m||pre.y==n)//只要碰到边界就可以了。
            return pre.step+1;
        for(int i=0;i<4;i++)
        {
            int mx=pre.x+dx[i],my=pre.y+dy[i];
            if(vis[mx][my]==false&&mx>=1&&mx<=m&&my>=1&&my<=n&&pre.step+1<num[mx][my]&&str[mx][my]!='#')//判断人可不可以走
            {
                node now;
                now.x=mx;now.y=my;now.step=pre.step+1;
                q.push(now);
                vis[mx][my]=true;
            }
        }
    }
    return -1;
}
int main()
{
    int T;
    scanf("%d",&T);
    while(T--)
    {
        cnt=0;
        scanf("%d%d",&m,&n);
        memset(num,INF,sizeof(num));
        memset(vis,false,sizeof(vis));
        for(int i=1;i<=m;i++)
            scanf("%s",str[i]+1);
        for(int i=1;i<=m;i++)
            for(int k=1;k<=n;k++)
            {
                if(str[i][k]=='F')
                {
                    F[++cnt].x=i;
                    F[cnt].y=k;
                    F[cnt].step=0;
                }
                if(str[i][k]=='J')
                {
                    Qiao.x=i;Qiao.y=k;
                    Qiao.step=0;
                }
            }
        queue<node>q;
        while(!q.empty()) q.pop();
        for(int i=1;i<=cnt;i++)
        {
            q.push(F[i]);
            num[F[i].x][F[i].y]=F[i].step;
        }
        while(!q.empty())//首先让火更新时间
        {
            node pre=q.front();q.pop();
            for(int i=0;i<4;i++)
            {
                int mx=pre.x+dx[i],my=pre.y+dy[i];
                if(mx>=1&&my>=1&&mx<=m&&my<=n&&str[mx][my]!='#'&&num[mx][my]==INF)//判断这里能不能更新
                {
                    node now;
                    now.x=mx;now.y=my;now.step=pre.step+1;
                    num[mx][my]=now.step;
                    q.push(now);
                }
            }
        }
        /*for(int i=1;i<=m;i++)
        {
            for(int k=1;k<=n;k++)
                printf("%d ",num[i][k]);
            printf("\n");
        }*/
        int ans=bfs();
        if(ans==-1) printf("IMPOSSIBLE\n");
        else printf("%d\n",ans);
    }
    return 0;
}

还有很多细节问题，具体问题可以评论交流，祝大家一次AC；