注意到

本题允许两种操作：

步行：向上下左右四个方向移动一格，不能进入障碍。

传送：当处于字母 c 时，可以一步到达所有与 c 相同的字母位置。

两种操作代价均为 1。

求从左上角 (1,1) 到右下角 (H,W) 的最短路径长度，无法到达则输出 -1。

该问题可抽象为无权无向图的单源最短路径问题。

解法

预处理：记录每个小写字母在网格中出现的所有位置。

初始化距离数组，起点距离为 0，其余为 -1（未访问）。

BFS队列从起点开始扩展：

(1) 向四个方向步行扩展，合法且未访问的格子更新距离并入队。

(2) 若当前格子是字母，则一次性扩展所有同字母位置，未访问则更新距离并入队，并清空该字母列表防止重复处理。

遍历结束后，终点的距离即为答案，若仍为 -1 则输出 -1。

C++解法

int n,m;
char t[1005][1005];
int dx[4]={-1,1,0,0};
int dy[4]={0,0,-1,1};
vec<pair<int,int>>zm[26];
int main()
{
    AC;
    cin>>n>>m;
    vec<vec<int>>ans(n+1,vec<int>(m+1,-1));
    ans.resize(n+1,vec<int>(m+1,-1));
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=m;j++)
        {
            cin>>t[i][j];
            if(t[i][j]>='a'&&t[i][j]<='z')  zm[t[i][j]-'a'].pb({i,j});
        }
    }
    queue<pair<pair<int,int>,int>>q;
    q.push({{1,1},0});
    ans[1][1]=0;
    while(!q.empty())
    {
        int x=q.front().first.first;
        int y=q.front().first.second;
        int d=q.front().second;
        q.pop();
        for(int i=0;i<4;i++)
        {
            int nx=x+dx[i];
            int ny=y+dy[i];
            if(nx>=1&&nx<=n&&ny>=1&&ny<=m&&t[nx][ny]!='#'&&ans[nx][ny]==-1)
            {
                ans[nx][ny]=ans[x][y]+1;
                q.push({{nx,ny},d+1});
            }
        }
        if(t[x][y]>='a'&&t[x][y]<='z')
        {
            int c=t[x][y]-'a';
            for(int i=0;i<(int)zm[c].size();i++)
            {
                int nx=zm[c][i].first;
                int ny=zm[c][i].second;
                if(ans[nx][ny]==-1)
                {
                    ans[nx][ny]=ans[x][y]+1;
                    q.push({{nx,ny},d+1});
                }
            }
            zm[c].clear();
        }
    }
    cout<<ans[n][m]<<endl;
    return 0;
}

Python 解法

from collections import deque
import sys
input=sys.stdin.read().split()
idx=0
n=int(input[idx])
m=int(input[idx+1])
idx+=2
g=[['']*(m+2)for _ in range(n+2)]
zm=[[]for _ in range(26)]
for i in range(1,n+1):
    s=input[idx]
    idx+=1
    for j in range(1,m+1):
        g[i][j]=s[j-1]
        if g[i][j].islower():
            c=ord(g[i][j])-ord('a')
            zm[c].append((i,j))
vis=[[-1]*(m+2)for _ in range(n+2)]
q=deque()
q.append((1,1,0))
vis[1][1]=0
dx=[-1,1,0,0]
dy=[0,0,-1,1]
while q:
    x,y,d=q.popleft()
    for i in range(4):
        nx=x+dx[i]
        ny=y+dy[i]
        if 1<=nx<=n and 1<=ny<=m and g[nx][ny]!='#' and vis[nx][ny]==-1:
            vis[nx][ny]=d+1
            q.append((nx,ny,d+1))
    if g[x][y].islower():
        c=ord(g[x][y])-ord('a')
        for nx,ny in zm[c]:
            if vis[nx][ny]==-1:
                vis[nx][ny]=d+1
                q.append((nx,ny,d+1))
        zm[c]=[]
print(vis[n][m])