思路与算法

把目标文本S加上末尾的Enter星号。无论怎样移动，选择字符总共必须花费|S|+1次，因此只需最小化方向键次数。

选择字符不会改变光标位置。如果当前字符就是下一个要选的字符，可以立即选择；把未来同一次选择提前，不改变任何方向键的执行条件，也不增加移动次数。同一字符连续出现多次时，可以在第一次到达时连续选完。所以代码保留原始选择次数，但把目标的连续相同字符压成一个，用这个压缩串描述移动阶段。

预处理每个格子四个方向上首个不同字符的位置，没有则视为不移动并跳过。状态为(已完成压缩字符数index,光标位置p)。从左上角开始，若它匹配首字符先消费。之后每按一个方向键跳到新格，如果匹配下一个压缩字符就立即使index加1，再进入下一状态。所有搜索边都是一次方向操作，用队列分层BFS，位集控制重复入队，第一次完成目标时得到最少移动数；加上固定选择次数即为答案。

正确性说明

任意合法方案都必须依次选择完整S及末尾星号，共|S|+1次，故比较总次数等价于比较方向次数。若当前位置已匹配下一个目标字符，而方案先移动再到别处选择同一字符，可以把该次选择提前到当前位置，并删去原来的选择；方向序列、方向键依赖的格子字符和选择后的未来文本均不变，因此移动次数不增加。对连续相同字符重复此交换即可立即全部消费。故存在遵守贪心消费规则的最优方案。

在此规则下，未来操作只依赖当前光标与尚未匹配的压缩后缀，状态定义完整。四个预处理跳跃精确符合逐格移动直到字符不同的操作；没有不同字符时的原地操作会多花一次却不改变状态，可从任何最优方案删掉，因此跳过不会影响答案。

初始状态完成所有免费于移动目标的首字符消费。每条BFS边恰对应一次合法方向键，且到达后消费匹配字符不计入移动目标成本；固定选择数将在末尾补回。队列按移动次数逐层扩展，入队即标记，同一状态第一次入队的移动次数最小。首次完成压缩串得到最少方向操作，结合固定选择成本就是原问题最少总操作数。

复杂度

令V=rc，原目标长度为L=|S|+1，压缩长度为R<=L。朴素四向跳跃预处理O(V(r+c))，目标压缩O(L)，位集初始化O(VR/64)。每个状态至多入队一次并检查4个方向，BFS总时间O(VR)。总时间O(V*(r+c)+VR+L)。跳跃表O(V)，已访问位集VR位；队列只保留当前前沿，若峰值为F则额外O(F)个整数，不保存历史出队状态或每状态int距离。总空间O(VR/64+F+V+L)个机器字。

易错点

1. 方向键一次跳到首个不同字符，不是固定移动一格，不能漏掉长相同字符带。
2. 压缩只用于移动阶段，最终仍要加原始|S|+1次选择，不能加压缩长度。
3. 开始位置固定左上角，可能一开始就匹配首目标。
4. Enter星号必须追加；若与前一字符相同，移动目标可压缩，但选择次数不减少。
5. 无效方向只会原地消耗一次，不会帮助最小化；入队时标记状态，避免指数重复搜索。
6. 现有10点包含50乘50键盘和长度10000文本，也包含长字符带、重复目标与公开19次样例。

参考代码（C++11）

#include <bits/stdc++.h>
using namespace std;
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int r, c;
    cin >> r >> c;
    vector<string> g(r);
    for (auto &s : g)
        cin >> s;
    string s;
    getline(cin, s);
    getline(cin, s);
    if (!s.empty() && s.back() == char(13))
        s.pop_back();
    int selections = s.size() + 1;
    s += '*';
    string text;
    for (char x : s)
        if (text.empty() || text.back() != x)
            text += x;
    int v = r * c;
    vector<array<int, 4>> next(v);
    int dx[] = {1, -1, 0, 0}, dy[] = {0, 0, 1, -1};
    for (int x = 0; x < r; x++)
        for (int y = 0; y < c; y++)
            for (int k = 0; k < 4; k++) {
                int a = x + dx[k], b = y + dy[k];
                while (a >= 0 && a < r && b >= 0 && b < c && g[a][b] == g[x][y]) {
                    a += dx[k];
                    b += dy[k];
                }
                next[x * c + y][k] = (a >= 0 && a < r && b >= 0 && b < c) ? a * c + b : x * c + y;
            }
    int start = (g[0][0] == text[0]);
    if (start == (int)text.size()) {
        cout << selections << '\n';
        return 0;
    }
    vector<unsigned long long> seen(((size_t)v * text.size() + 63) / 64);
    queue<int> q;
    int id = start * v;
    seen[id >> 6] |= 1ULL << (id & 63);
    q.push(id);
    int moves = 0;
    while (!q.empty()) {
        int size = q.size();
        while (size--) {
            int id = q.front();
            q.pop();
            int p = id % v, index = id / v;
            for (int z : next[p])
                if (z != p) {
                    int j = index + (g[z / c][z % c] == text[index]);
                    if (j == (int)text.size()) {
                        cout << selections + moves + 1 << '\n';
                        return 0;
                    }
                    int key = j * v + z;
                    if (!(seen[key >> 6] >> (key & 63) & 1)) {
                        seen[key >> 6] |= 1ULL << (key & 63);
                        q.push(key);
                    }
                }
        }
        moves++;
    }
    cout << -1 << '\n';
}