If the size of maze is small enough, the problem can be solved with a simple BFS (Breadth-First Search). However, since there are \(O(HW)\) cells and each cell has \(O(HW)\) possible transitions (the cells to which you can directly reach in one move) including Walk and Warp, the total time complexity becomes \(O(H^2W^2)\), which is difficult to meet the time limit under the constraints of the problem.

Here, notice the following fact:

• Suppose you are currently at a Warp cell during the BFS. If you have already visited a Warp cell with the same character as the current cell, you do not need to consider Warps from the current cell.

This is because, rather than Warping from the current cell, it is better to Warp from the already-visited cell.

Therefore, the transitions need to be processed, for each letter, when visiting the cell with that character for the first time; this way, the total complexity becomes \(O(\sigma HW)\), where \(\sigma\) is the size of the alphabet, which is fast enough.

Sample code (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;
}