after与迷宫

这题比较坑的是题意难理解。我是没从题目中理解出F和M同时出现才会变成机器人，QAQ。
理解出来就好办了，可以用双向bfs，也可单向bfs；
最后求出的路径×2；

#include<bits/stdc++.h>
using namespace std;
int n,m,mp[1001][1001],vis[1000010],r,c;
int d[4][2]={{0,1},{0,-1},{-1,0},{1,0}};
struct node{
    int cnt;
}node[1000010];//cnt记录这个路径上是否已经走过F或M，-1为F,-2为M
void bfs(int s)
{
    queue<int> q;
    q.push(s);
    vis[s]=0;
    while(!q.empty())
    {
        int k=q.front();q.pop();
        int x=k/m,y=k%m;
        if(x==r&&y==c) return;
        for(int i=0;i<4;i++)
        {
            int dx=x+d[i][0],dy=y+d[i][1];
            if(dx<0||dy<0||dx>=n||dy>=m) continue;
            if(mp[dx][dy]==0||vis[dx*m+dy]) continue;
            if(node[x*m+y].cnt!=mp[dx][dy]&&mp[dx][dy]<0&&node[x*m+y].cnt<0) continue;//一条路径上F和M只能经过一种，判断（x，y）结点是否已经经过一种，如果（dx，dy）是F或M的一种，判断是否相同
            node[dx*m+dy].cnt=node[x*m+y].cnt;//该路径所经过的F/M往下传
            if(mp[dx][dy]<0) node[dx*m+dy].cnt=mp[dx][dy];
            vis[dx*m+dy]=vis[x*m+y]+1;
            q.push(dx*m+dy);
        }
    }
}
int main()
{
    int t;
    cin>>t;
    while(t--){
        memset(mp,0,sizeof(mp));
        memset(vis,0,sizeof(vis));
        memset(node,0,sizeof(node));
        cin>>n>>m>>r>>c;
        for(int i=0;i<n;i++)
        {
            for(int j=0;j<m;j++)
            {
                char ch;
                cin>>ch;
                if(ch=='.') mp[i][j]=1;
                if(ch=='F') mp[i][j]=-1;
                if(ch=='M') mp[i][j]=-2;
            }
        }
        int s=0;r-=1,c-=1;
        bfs(s);
        if(r*m+c==s||vis[r*m+c]) cout<<2*vis[r*m+c]<<endl;//如果算法书恰好在入口或能够到达
        else cout<<"IMPOSSIBLE"<<endl;
    }
}