遗迹

思路与复杂度

状态为位置和已经使用过的传送门集合。普通移动代价1，使用尚未使用的传送门代价0并更新集合，使用0-1 BFS。零代价转移只能在到达该传送门后发生；传送后该类门已标记，不能重复使用。首次获得的最优距离由0-1 BFS的距离松弛保证。时间与空间 O(nm·2^p)。

正确性与边界

每条合法路线对应状态图中的一条同代价路径，传送位掩码恰好限制每类门使用次数。

参考代码

#include <bits/stdc++.h>
using namespace std;
int main(){ios::sync_with_stdio(false);cin.tie(nullptr);int n,m;cin>>n>>m;vector<string>a(n);for(auto&s:a)cin>>s;vector<vector<pair<int,int>>>pos(8);int S=-1,T=-1;for(int i=0;i<n;i++)for(int j=0;j<m;j++){char c=a[i][j];if(c=='S')S=i*m+j;else if(c=='T')T=i*m+j;else if(c>='A'&&c<='H')pos[c-'A'].push_back({i,j});}int id[8],p=0;fill(id,id+8,-1);for(int c=0;c<8;c++)if(!pos[c].empty())id[c]=p++;int cells=n*m,total=cells*(1<<p);vector<int>dist(total,-1),q;q.reserve(total);size_t head=0;auto enc=[&](int v,int mask){return mask*cells+v;};dist[enc(S,0)]=0;q.push_back(enc(S,0));int dx[4]={-1,0,1,0},dy[4]={0,1,0,-1};while(head<q.size()){int s=q[head++],mask=s/cells,v=s%cells,cd=dist[s];if(v==T){cout<<cd<<"\n";return 0;}int x=v/m,y=v%m;for(int z=0;z<4;z++){int nx=x+dx[z],ny=y+dy[z];if(nx<0||nx>=n||ny<0||ny>=m||a[nx][ny]=='#')continue;int nv=nx*m+ny,s1=enc(nv,mask);if(dist[s1]<0)dist[s1]=cd+1,q.push_back(s1);char c=a[nx][ny];if(c>='A'&&c<='H'&&id[c-'A']>=0){int b=id[c-'A'];if(!(mask>>b&1)){auto &w=pos[c-'A'];auto o=(w[0].first==nx&&w[0].second==ny)?w[1]:w[0];int s2=enc(o.first*m+o.second,mask|(1<<b));if(dist[s2]<0)dist[s2]=cd+1,q.push_back(s2);}}}}cout<<-1<<"\n";}