解救小Q UESTC - 149

今天药忘吃喽~ 2022-06-14 10:38 116阅读 0赞

### **解救小Q UESTC - 149** ###

--------------------

#### **Problem** ####

小Q被邪恶的大魔王困在了迷宫里，love8909决定去解救她。 迷宫里面有一些陷阱，一旦走到陷阱里，就会被困身亡:(，迷宫 里还有一些古老的传送阵，一旦走到传送阵上，会强制被传送到 传送阵的另一头。

现在请你帮助love8909算一算，他至少需要走多少步才能解 救到小Q？

#### **Input** ####

第一行为一个整数TT，表示测试数据组数。

每组测试数据第一行为两个整数NN，MM，(1≤N,M≤501≤N,M≤50)表示 迷宫的长和宽。

接下来有NN行，每行MM个字符，是迷宫的具体描述。

.表示安全的位置

# 表示陷阱， #

Q表示小Q的位置  
L表示love8909所在位置，  
数据保证love8909只有一个，数据也保证小Q只有一个。

小写字母a-z表示分别表示不同的传送阵，数据保证传送阵 两两配对。

#### **Output** ####

每组数据输出一行，解救小Q所需的最少步数，如果无论如何都 无法救小Q，输出-1。

#### **Sample Input** ####

5 5  
….L  
.\#\#\#.  
b\#b\#a

## . ##

…Qa

5 5  
….L  
.\#\#\#.  
.\#.\#.

## . ##

…Q.

#### **Sample Output** ####

3  
\-1

#### ps：传送门很烦 ####

代码如下：

#include<iostream>
    #include<cstdio>
    #include<cstring>
    #include<queue>
    using namespace std;
    
    struct pos
    {
        int x;
        int y;
        pos(int x=-1,int y=-1):x(x),y(y){}
    };
    
    bool operator == (const pos &a,const pos &b)
    {
        return a.x==b.x&&a.y==b.y;
    }
    
    const int dir[4][2] = {-1,0,0,1,1,0,0,-1};
    int n, m;
    bool judge(pos a)
    {
        if(a.x<0||a.x>=n)return 0;
        if(a.y<0||a.y>=m)return 0;
        return 1;
    }
    
    char maze[55][55];
    pos gate[30][2];
    pos start;
    pos fin;
    int dis[55][55];
    
    void bfs()
    {
        queue<pos> q;
        while(!q.empty())q.pop();
        dis[start.x][start.y]=0;
        q.push(start);
        while(!q.empty())
        {
            pos now=q.front();
            q.pop();
            for(int d=0;d<4;++d)
            {
                pos to;
                to.x=now.x+dir[d][0];
                to.y=now.y+dir[d][1];
                if(!judge(to))continue;
                if(maze[to.x][to.y] == '#')continue;
                int far=dis[now.x][now.y]+1;
                if(maze[to.x][to.y]>='a'&&maze[to.x][to.y]<='z') {
                    int ch = maze[to.x][to.y]-'a';
                    if(to==gate[ch][1])
                    {
                            to=gate[ch][0];
                    }
                    else{
                           to=gate[ch][1];
                    }
                }
                if(dis[to.x][to.y]>far||dis[to.x][to.y]== -1) {
                    dis[to.x][to.y] = far;
                    q.push(to);
                }
            }
        }
    }
    
    int main()
    {
    // freopen("data.txt","r",stdin);
        int T;
        scanf("%d",&T);
        while(T--)
        {
            scanf("%d%d",&n,&m);
            memset(dis,-1,sizeof(dis));
            for(int i=0;i<30;++i)
                gate[i][0]=gate[i][1]=pos(-1,-1);
            for(int i=0;i<n;++i) {
                scanf("%s",maze[i]);
                while(strlen(maze[i])!=m)scanf("%s",maze[i]);
                for(int j=0;j<m;++j) {
                    if(maze[i][j]=='Q') {
                            fin.x=i;
                            fin.y=j;
                    }
                    else if(maze[i][j]=='L') {
                            start.x=i;
                            start.y=j;
                    }
                    else if(maze[i][j]>='a'&&maze[i][j]<='z') {
                        int tmp=maze[i][j]-'a';
                        if(gate[tmp][0].x==-1) {
                            gate[tmp][0]=pos(i,j);
                        }
                        else {
                             gate[tmp][1]=pos(i,j);
                        }
                    }
                }
            }
            bfs();
            printf("%d\n",dis[fin.x][fin.y]);
        }
        return 0;
    }