迷路の大きさが小さい場合は単純な BFS (幅優先探索) によって解くことができます。しかし、マスの数が \(O(HW)\)、各マスからの遷移の数（今のマスから \(1\) 回の行動で到達できるマスの数）が歩行・ワープ合わせて \(O(HW)\) あることから、全体の計算量は \(O(H^2W^2)\) となり、本問題の制約下では間に合いません。

ここで、以下の事実が成立することに着目します。

• BFS の過程においてあるワープマスを訪れたとする。もし、このワープマスと同じ文字が書かれた別のワープマスに既に訪れたことがあるのであれば、今訪れているマスからのワープについては考える必要がない。

なぜならば、今訪れているマスからワープをするよりも、既に訪れた同じ文字のワープマスからワープをした方が得だからです。

よって、ワープに対応する遷移は各文字ごとに最初に訪れたマスのみから行えばよいため、全体の計算量は文字の種類数を \(\sigma\) として \(O(\sigma HW)\) となり、十分高速です。

実装例 (C++) :

#include <bits/stdc++.h>

using namespace std;

const int inf = 1 << 30;

const int dx[] = {1, 0, -1, 0};
const int dy[] = {0, 1, 0, -1};

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int h, w;
    cin >> h >> w;
    vector<string> s(h);
    vector<vector<pair<int, int>>> ls(26);
    for (int i = 0; i < h; i++) {
        cin >> s[i];
        for (int j = 0; j < w; j++) {
            if (islower(s[i][j])) {
                ls[s[i][j] - 'a'].emplace_back(i, j);
            }
        }
    }

    vector d(h, vector<int>(w, inf));
    queue<pair<int, int>> q;
    vector<bool> seen(26);
    d[0][0] = 0;
    q.emplace(0, 0);
    while (!q.empty()) {
        auto [i, j] = q.front();
        q.pop();
        for (int k = 0; k < 4; k++) {
            int ni = i + dx[k];
            int nj = j + dy[k];
            if (ni < 0 or ni >= h or nj < 0 or nj >= w) continue;
            if (s[ni][nj] == '#') continue;
            if (d[ni][nj] == inf) {
                d[ni][nj] = d[i][j] + 1;
                q.emplace(ni, nj);
            }
        }
        if (islower(s[i][j])) {
            int c = s[i][j] - 'a';
            if (seen[c]) continue;
            seen[c] = true;
            for (auto [ni, nj]: ls[c]) {
                if (d[ni][nj] == inf) {
                    d[ni][nj] = d[i][j] + 1;
                    q.emplace(ni, nj);
                }
            }
        }
    }

    int ans = d[h - 1][w - 1];
    cout << (ans == inf ? -1 : ans) << endl;
}