after与迷宫

链接：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”(不带引号)。

solution：

首先题目有个小细节，after在只有遇到M和F才会变成超级YK机器人，只遇到其中一个只会变成YK机器人，但是其实通过样例我们也可以推出“超级”这个小细节。
我们可以进行两次遍历，一次是可以通过M而不能通过F，另一次则能通过F而不能通过M，取两次遍历的最小值，存在则把这个最小值*2，不存在输出IMPOSSIBLE

#include<bits/stdc++.h>
using namespace std;
#define INF 0x3f3f3f3f
typedef pair<int,int> P;
int t,n,m,r,c;
int dx[]={1,-1,0,0},dy[]={0,0,1,-1};
char tu[1005][1005];
int d[1005][1005];

int bfs()
{
    queue <P> q;
    q.push(P(0,0));
    memset(d,INF,sizeof(d));
    d[0][0]=0;
    while(!q.empty())
    {
        P p=q.front();q.pop();
        for(int i=0;i<4;i++)
        {
            int x=p.first+dx[i],y=p.second+dy[i];
            if(x<0||x>=n||y<0||y>=m)continue;
            if(tu[x][y]=='*'||tu[x][y]=='M'||d[x][y]!=INF)continue;
            d[x][y]=d[p.first][p.second]+1;
            q.push(P(x,y));
        }
    }
    int max1=d[r][c];
    q.push(P(0,0));
    memset(d,INF,sizeof(d));
    d[0][0]=0;
    while(!q.empty())
    {
        P p=q.front();q.pop();
        for(int i=0;i<4;i++)
        {
            int x=p.first+dx[i],y=p.second+dy[i];
            if(x<0||x>=n||y<0||y>=m)continue;
            if(tu[x][y]=='*'||tu[x][y]=='F'||d[x][y]!=INF)continue;
            d[x][y]=d[p.first][p.second]+1;
            q.push(P(x,y));
        }
    }
    return min(max1,d[r][c]);
}

int main()
{
    cin>>t;
    while(t--)
    {
        cin>>n>>m>>r>>c;
        r--;
        c--;
        for(int i=0;i<n;i++)
            cin>>tu[i];
        int s=bfs();
        if(s==INF)
            cout<<"IMPOSSIBLE\n";
        else
            cout<<s*2<<endl;
    }
}