思路

题意简述：在 $n\times m$ 的网格中，从入口 ! 走到出口 @。途中有四种遗印 0~3，必须全部收集后才能到达出口；成对出现的小写字母是传送符文，踩上去会立即瞬移到同字母的另一端，仍只算一步。求最少步数，无解输出 -1。

只有“位置 + 已收集遗印集合”会影响后续能走的路，因此把状态定义为 $(x,y,\text{mask})$，其中 mask 是一个 4 位二进制数：

• 第 $i$ 位为 1 表示已经收集了遗印 $i$（$i=0,1,2,3$）；
• 起点状态为 $(s_x,s_y,0)$，目标状态为 $(e_x,e_y,15)$，因为 $1111_2=15$。

状态总数为 $16nm$，每条边（走一步）的代价都是 1，所以在状态图上做普通 BFS，第一次弹出目标状态时的距离就是最短路。

具体做法：

1. 读图时把地图四周额外补一圈 #，这样判断越界只需检查是否为 #。
2. 用 pos[c] 收集每个小写字母的所有坐标；若某字母恰好出现两次，就建立双向传送映射 door 并标记 hasDoor。只出现一次的字母只是普通可通行格子。
3. BFS 转移：从当前状态向上下左右扩展一格。
   • 新格子是 # 则跳过；
   • 新格子是数字 0~3，把对应位并进 mask；
   • 新格子是成对符文，则把坐标直接换成它的另一端（瞬移与移动合并为一步）；
   • 若新状态 $(nx,ny,nsta)$ 未被访问，则标记访问、记录距离并入队。
4. 队列为空仍未到达目标，输出 -1。

正确性：每个合法的移动/瞬移都对应状态图中的一条边，且每条边代价相同。BFS 按距离非降序扩展，每个状态第一次被访问时得到的就是到该状态的最短距离；第一次弹出 $(e_x,e_y,15)$ 自然就是收集全部遗印后到达出口的最少步数。

复杂度：状态数 $O(16nm)$，每个状态常数条转移，时间 $O(nm)$（常数约 64）；空间为 vis、dista 等数组，同为 $O(16nm)$。

代码

#include<bits/stdc++.h>
#define int long long
#define dd double
#define str string
#define el cout << '\n'
#define re return
#define ff first
#define ss second
#define pll pair<int,int>
using namespace std;

// 地图，四周额外留一圈墙，省去越界判断
static char a[1012][1012];
// vis[x][y][mask]：是否到达过 (x,y)，且遗印收集状态为 mask
static bool vis[1012][1012][16];
// dista[x][y][mask]：该状态的最短步数
static int dista[1012][1012][16];
// door[x][y]：该格传送符文的另一端坐标
static pll door[1012][1012];
// hasDoor[x][y]：该格是否为成对符文，可传送
static bool hasDoor[1012][1012];

void go(){
    int n,m;cin>>n>>m;

    int sx=0,sy=0,ex=0,ey=0;

    // pos[c] 记录字母 c 出现过的所有坐标，用于判断是否恰好成对
    vector<pll> pos[256];

    // 把 0..n+1 行、0..m+1 列全部初始化为墙，并清空访问标记
    for(int i=0;i<=n+1;i++){
        for(int j=0;j<=m+1;j++){
            a[i][j] = '#';
            hasDoor[i][j] = false;
            vis[i][j][0] = vis[i][j][1] = vis[i][j][2] = vis[i][j][3] =
            vis[i][j][4] = vis[i][j][5] = vis[i][j][6] = vis[i][j][7] =
            vis[i][j][8] = vis[i][j][9] = vis[i][j][10] = vis[i][j][11] =
            vis[i][j][12] = vis[i][j][13] = vis[i][j][14] = vis[i][j][15] = false;
        }
    }

    // 读入地图，同时记录起点、终点以及每个字母的坐标
    for(int i=1;i<=n;i++){
        str s;cin>>s;
        for(int j=1;j<=m;j++){
            char c = s[j-1];
            a[i][j] = c;

            if ('a' <= c && c <= 'z'){
                pos[(unsigned char)c].push_back({i,j});
            }
            else if (c=='!') sx=i, sy=j;
            else if (c=='@') ex=i, ey=j;
        }
    }

    //---------------- 建立传送门
    // 只有恰好出现两次的字母才构成传送对，两端互相指向
    for(int c='a'; c<='z'; c++){
        if(pos[c].size() == 2){
            pll p1 = pos[c][0], p2 = pos[c][1];
            door[p1.ff][p1.ss] = p2;
            door[p2.ff][p2.ss] = p1;
            hasDoor[p1.ff][p1.ss] = true;
            hasDoor[p2.ff][p2.ss] = true;
        }
    }

    //---------------- 宽度优先搜索求最短路
    // 四个移动方向
    static int dx[4] = {1,-1,0,0};
    static int dy[4] = {0,0,1,-1};

    // 状态队列：(行, 列, 遗印掩码)
    queue<tuple<int,int,int>> q;
    q.push({sx, sy, 0});
    vis[sx][sy][0] = true;
    dista[sx][sy][0] = 0;

    while(!q.empty()){
        auto [x, y, sta] = q.front();
        q.pop();

        // 集齐 0/1/2/3 且站在出口，当前距离即最短答案
        if(sta == 15 && x==ex && y==ey){
            cout << dista[x][y][sta] << "\n";
            return;
        }

        for(int i=0;i<4;i++){
            int nx = x + dx[i];
            int ny = y + dy[i];

            // 墙（含地图外的补边）不可进入
            if (a[nx][ny] == '#') continue;

            int nsta = sta;
            char c = a[nx][ny];

            // 踩到遗印，把对应二进制位设为 1
            if ('0' <= c && c <= '3'){
                nsta |= 1 << (c - '0');
            }

            // 踩到成对符文，立即瞬移到另一端，仍只算一步
            if(hasDoor[nx][ny]){
                auto [tx, ty] = door[nx][ny];
                nx = tx; ny = ty;
            }

            // 新状态未访问过才入队；BFS 保证首次到达即最短
            if(!vis[nx][ny][nsta]){
                vis[nx][ny][nsta] = true;
                dista[nx][ny][nsta] = dista[x][y][sta] + 1;
                q.push({nx, ny, nsta});
            }
        }
    }

    // 队列耗尽仍未到达目标状态
    cout << -1 << "\n";
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    // 本题只有一组数据
    go();
    return 0;
}