链接：https://ac.nowcoder.com/acm/problem/14608

题目描述

after的算法书的遗落在一个叫做AIJ的迷宫中了，这个迷宫有N*M个房间，迷宫的入口为(1，1)，算法书遗落在(r，c)。迷宫中的房间有四种状态：空房间、无法进入的房间、有墨菲斯托存在的房间和有莉莉丝存在的房间。墨菲斯托会否定一切，而莉莉丝会诱惑人做一种叫做YK的活动。after是一个意志薄弱的人，他遇到了墨菲斯托和莉莉丝之后，便会变成眼神空洞的超级YK机器人。after每步可以从他当前的房间走至上下左右四个房间的其中一个房间。after害怕变成超级YK机器人，所以要尽快拿到算法书然后从入口逃离。问after最少需要走多少步才可以在不变成超级YK机器人的情况下从入口出发取回算法书并逃离迷宫？

输入描述:

第一行一个正整数T(T<=10)，表示共有T组数据。
对于每组数据，第一行四个正整数N，M，r，c(1<=N,M<=1000；1<=r<=N；1<=c<=M)。
接下来N行，每行M个字符，每个表示房间的状态，“.”表示空房间，“*”表示无法进入的房间，“F”表示有墨菲斯托存在的房间，“M”表示有莉莉丝存在的房间。
数据保证(1，1)为“.”。

标题输出描述:

对每组数据输出一行，即after最少需要走的步数。若after无法取回算法书，则输出“IMPOSSIBLE”(不带引号)。

示例1
输入
复制
1
4 4 4 3
..*
*F..
*..
*M.F
输出
14

思路

本题说不能同时经过M与F,那么我们就可以经过M与F中的一个，所以我们用两次bfs，一次将M设置为可以走，一次将F设置为可以走。最后在来找两次中走的步数少的就好了。具体的可以看代码中的注释。

#include<iostream>
#include<queue>
#include<cstring>
#include<string.h>
#include<cmath>
using namespace std;
struct Node{
    int x,y;//坐标 
    int step;//步数 
}qq,zz;
int xx[]={-1,0,0,1};
int yy[]={0,-1,1,0};//四个方向 
int vis[1005][1005];
char s1[1005][1005],s[1005][1005];
int n,m,r,c;
int bfs(int qx,int qy,int zx,int zy){
    queue<Node>q;
    Node qq;
    qq.x=1;qq.y=1;qq.step=0;
    q.push(qq);
    vis[1][1]=1;
    while(!q.empty()){
        Node now=q.front();
        q.pop();
        if(now.x==zx&&now.y==zy){
            return now.step;
        }//如果到达，则返回当前步数 
        for(int i=0;i<4;i++){
            qq.x=now.x+xx[i];
            qq.y=now.y+yy[i];
            if(qq.x>0&&qq.y>0&&qq.x<=n&&qq.y<=m&&s1[qq.x][qq.y]=='.'&&!vis[qq.x][qq.y]){
                vis[qq.x][qq.y]=1;
                qq.step=now.step+1;
                q.push(qq);
            }//如果可以到达，则标记为已经走过，步数为当前步数+1，并将结构体加入到队列中 
        }
    }
    return -1;//若q为空也没到达，则返回-1 
} 
int main(){
    int t;
    cin>>t;
    while(t--){
        cin>>n>>m>>r>>c;
        for(int i=1;i<=n;i++){
            for(int j=1;j<=m;j++){
                cin>>s[i][j];
                if(s[i][j]=='F'){
                    s1[i][j]='.';
                }
                else{
                    s1[i][j]=s[i][j];
                }//将s1置为.与F可走 
            }
        }
        memset(vis,0,sizeof(vis));
        int a1=bfs(1,1,r,c);
        for(int i=1;i<=n;i++){
            for(int j=1;j<=m;j++){
                if(s[i][j]=='M'){
                    s1[i][j]='.';
                }
                else{
                    s1[i][j]=s[i][j];
                }//将s1置为.与M可走 
            }
        }
        memset(vis,0,sizeof(vis));
        int a2=bfs(1,1,r,c);
        if(a1==-1&&a2==-1){
            cout<<"IMPOSSIBLE"<<endl;
        }//如果都小于0，则不肯能到达r,c 
        else if(a1<0||a2<0){
            cout<<max(a1,a2)*2<<endl;
        }//如果有一个小于0，则答案为大于0的 
        else{
            cout<<min(a1,a2)*2<<endl;
        }//如果答案都大于0，则为步数小的
        //因为是来回，所以答案乘2 
    } 
    return 0;
}