spfa求调 玄关

#include<bits/stdc++.h>
using namespace std;
int n,m,S,T;
struct Edge{
	int v,w;
};
vector<Edge> g[100005];
char s[305][305];
int dx[5]={0,1,-1,0,0};
int dy[5]={0,0,0,1,-1};
int t[1145];
int id(int i,int j){
    return (i-1)*m+j;
}
int dis[100005];
bool f[100005];
void spfa(int st){
    memset(dis,0x3f,sizeof(dis));
    memset(f,0,sizeof(f));
    dis[st]=0;
    queue<int> q;
    q.push(st);
    while(!q.empty()){
        int x=q.front();
        q.pop();
        f[x]=0;
        for(auto [y,w]:g[x]){
            if(dis[y]>dis[x]+w){
                dis[y]=dis[x]+w;
                if(!f[y]){
                    f[y]=1;
                    q.push(y);
                }
            }
        }
    }
}
int main(){
	scanf("%d %d",&n,&m);
	for(int i=1;i<=n;i++){
		for(int j=1;j<=m;j++){
			cin>>s[i][j];
		}
	}
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            if(s[i][j]=='#'){
                continue;
            }
            for(int k=1;k<=4;k++){
                int xx=i+dx[k],yy=j+dy[k];
                if(xx<1||xx>n||yy<1||yy>m||s[xx][yy]=='#'){
                    continue;
                }
                g[id(i,j)].push_back({id(xx,yy),1});
                g[id(xx,yy)].push_back({id(i,j),1});
            }
            if(s[i][j]=='@'){
                S=id(i,j);
            }
            if(s[i][j]=='='){
                T=id(i,j);
            }
            if(s[i][j]>='A'&&s[i][j]<='Z'){
            	if(t[s[i][j]]){
                    g[t[s[i][j]]].push_back({id(i,j),0});
                    g[id(i,j)].push_back({t[s[i][j]],0});
                }
                t[s[i][j]]=id(i,j);
			}
        }
    }
    spfa(S);
    printf("%d",dis[id(4,28)]);
//    printf("%d",dis[T]);
	return 0;
}