NC14608. after与迷宫
描述
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
C++ 解法, 执行用时: 13ms, 内存消耗: 4396K, 提交时间: 2022-06-10 21:40:44
#include<bits/stdc++.h>
#define inf 0x3f3f3f3f
#define N 1010
using namespace std;
typedef pair<int,int> pii;
int n,m,T,r,c,i,j;
char g[N][N];
int d[N][N];
void bfs(char c)
{
queue<pii>q;
memset(d,inf,sizeof d);
q.push({0,0});
d[0][0]=0;
int dx[4]={1,0,-1,0},dy[4]={0,1,0,-1};
while(q.size()){
auto t =q.front();
q.pop();
int sx =t.first,sy=t.second;
for(int i=0;i<4;i++){
int x =sx+dx[i],y=sy+dy[i];
if(x>=0 && x<n && y>=0 && y<m && d[x][y]==inf && (g[x][y]=='.' || g[x][y]==c)){
d[x][y]=d[sx][sy]+1;
q.push({x,y});
}
}
}
}
int main(){
cin>>T;
while(T--){
cin>>n>>m>>r>>c;
for(int i=0;i<n;i++)
for(int j=0;j<m;j++)
cin>>g[i][j];
bfs('F');
int x =d[r-1][c-1];
bfs('M');
int y= d[r-1][c-1];
int z =min(x,y);
if(z == inf)cout<<"IMPOSSIBLE"<<endl;
else cout<<2*z<<endl;
}
}