A137132 传送门迷宫 题解

Solution

看到“迷宫”二字，就想起了 BFS，所以我们使用 BFS 来做。

现在考虑：如何存储传送门？

我们可以建立 $26$ 个 vector，分别存储每一个字母出现的位置。

在 BFS 过程中，判断这个点是否为传送门，然后将 传送门可以传送到的位置 都加入到队列内就可以了。

为什么不用 pair？

题目内没有说 保证一种传送门只出现 $2$ 次，所以不能用 pair。

AC Code

#include <iostream>
#include <queue>
#include <vector>
#include <cctype>
using namespace std;
const int N = 1002;
char a[N][N];
bool vis[N][N];
int n,m;
struct Pos{ int x,y,step; };
int sx,sy,ex,ey;
int dx[4]={-1,1,0,0};
int dy[4]={0,0,-1,1};
vector<pair<int,int>> portal[26]; // 存储每个字母的所有位置
bool used[26]; // 标记该字母传送是否已经处理过
int main(){
    cin>>n>>m;
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            cin>>a[i][j];
            if(a[i][j]=='S') sx=i,sy=j;
            else if(a[i][j]=='T') ex=i,ey=j;
            else if(islower(a[i][j])){ // 小写字母
                portal[a[i][j]-'a'].push_back({i,j});
            }
        }
    }

    queue<Pos> q;
    q.push({sx,sy,0});
    vis[sx][sy]=true;
    while(!q.empty()){
        Pos now=q.front(); q.pop();
        if(now.x==ex && now.y==ey){
            cout<<now.step;
            return 0;
        }
        // 四个方向移动
        for(int i=0;i<4;i++){
            int nx=now.x+dx[i], ny=now.y+dy[i];
            if(nx>=1 && nx<=n && ny>=1 && ny<=m && !vis[nx][ny] && a[nx][ny]!='#'){
                vis[nx][ny]=true;
                q.push({nx,ny,now.step+1});
            }
        }
        // 如果当前格子是传送门字母
        if(islower(a[now.x][now.y])){
            int id = a[now.x][now.y]-'a';
            if(!used[id]){
                used[id]=true;
                for(auto p:portal[id]){
                    if(!vis[p.first][p.second]){
                        vis[p.first][p.second]=true;
                        q.push({p.first,p.second,now.step+1});
                    }
                }
            }
        }
    }
    cout<<-1;
    return 0;
}

$\text{0v0 I AK IOI}$