昨天ABC D题，一直TLE，求调

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=1005;
int n,m,dis[N][N],vis[N][N]; 
char a[N][N];
vector<pair<int,int> > g[40];
queue<pair<int,int> > q;
const int dx[4]={0,1,0,-1};
const int dy[4]={1,0,-1,0};
bool check(int r,int c){
	if(r<1 || r>n || c<1 || c>m || a[r][c]=='#') return false;
	return true;
}
signed main(){
	ios::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);
	cin>>n>>m;
	for(int i=1;i<=n;i++)
		for(int j=1;j<=m;j++){
			cin>>a[i][j];
			if(islower(a[i][j])) g[a[i][j]-'a'].push_back({i,j});
		}
	q.push({1,1}); 
	memset(dis,0x3f3f3f,sizeof(dis));
	dis[1][1]=0;
	while(!q.empty()){
		pair<int,int> u=q.front();
		q.pop();
		int x=u.first,y=u.second;
		if(x==n && y==m){
			cout<<dis[n][m]<<'\n';
			return 0;
		}
		if(vis[x][y]) continue;
		vis[x][y]=1;
		for(int i=0;i<=3;i++){
			int tx=x+dx[i],ty=y+dy[i];
			if(check(tx,ty) && dis[tx][ty]==4557430888798830399){
				if(dis[x][y]+1<dis[tx][ty]){
					dis[tx][ty]=dis[x][y]+1,q.push({tx,ty});
				}
			}
		}
		if(islower(a[x][y])){
			char c=a[x][y];
			for(auto v:g[c-'a']){
				int tx=v.first,ty=v.second;
				if(check(tx,ty) && dis[tx][ty]==4557430888798830399) dis[tx][ty]=dis[x][y]+1,q.push({tx,ty});
			}
		}
	}
	cout<<-1<<'\n';
	return 0;
}