本文共 2480 字，大约阅读时间需要 8 分钟。

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”(不带引号)。 示例1 输入 复制 1 4 4 4 3 …** *F… .. *M.F 输出 复制 14

先贴代码：

#include
   
    using namespace std;typedef long long ll;const int maxn = 1e3+5;const int INF = 0x3f3f3f3f;char g[maxn][maxn];bool vis[maxn][maxn];int X[4] = {   0,1,0,-1};int Y[4] = {   1,0,-1,0};int m,n,dx,dy;int t,flag;int res ,ans;struct node{       int x;    int y;    int dis;    char c;}Node;bool check(int x,int y,char c){       if(x<1||x>n||y<1||y>m) return false;    if(vis[x][y]||g[x][y]=='*') return false;    if((g[x][y]=='M'&&c=='F')||(g[x][y]=='F'&&c=='M')) return false;    return true;}void bfs(int x,int y){       queue
    
     q;    Node.x = x,Node.y = y;    Node.dis = 0,Node.c = '.';    q.push(Node);    vis[x][y] = true;    while(!q.empty())    {           node temp = q.front();        q.pop();        if(temp.x==dx&&temp.y==dy)        {               if(temp.c=='F')ans = temp.dis;            if(temp.c=='M')res = temp.dis;            if(temp.c=='.')res = temp.dis;            flag = 1;        }        for(int i=0;i<4;i++)        {               int newx = temp.x + X[i];            int newy = temp.y + Y[i];            if(check(newx,newy,temp.c))//队首的字母             {                   //cout<
     
      <<" "<
      
       <
       
        >t;    while(t--)    {           memset(vis,false,sizeof(vis));        flag=0,ans = INF,res = INF;        cin>>n>>m>>dx>>dy;        for(int i=1;i<=n;i++)        {               for(int j=1;j<=m;j++)            {                   cin>>g[i][j];            }        }        bfs(1,1);        if(flag) cout<
        
         <<"\n"; else cout<<"IMPOSSIBLE"<<"\n"; } return 0;}/*24 4 4 3..***F..*.*.*M.F4 4 4 4..***.F.*M*M*.F.3 3 3 3.F.M*M.F.*/
        
       
      
     
    
   

思路：

1.可以跑两遍bfs

第一遍把F设为可走，第二遍把M设为可走，取两者的最小值即可，如果都没有找到，结果就是不可能。

2.跑一遍bfs

每次把当前节点设为 包括该点和之前走过的路径的记录

下面的调式输出为：

– 队首节点的node.c

– 当前节点的坐标

– 当前节点的node.c

Node.c表示当前节点和之前的路径上的节点的标志，

---

如需获取更多资料，关注公众号回复关键字领取。