Keyboarding

一本通·提高篇 · 代码 · cpp · 难度 5/5 · 共 2528 字
预处理跳转表，逐字符做多源最短路
一本通
练习
正文

// 原题：https://oj.yecheng.tv/p/T1452
// 题意：r * c 的虚拟键盘上，光标初始在左上角，方向键会跳到该方向上第一个与当前字符不同的格子（不存在则不动），选择键打印当前字符，求打印文本（含结尾换行）的最少按键次数。
// 思路：预处理跳转表 + 逐字符 DP。
// 1. 先算出每个格子按四个方向键后会落到哪里，跳过的正是与当前字符相同的一段连续格子。
// 2. 设 cur[p] 为「打印完当前前缀后停在 p」的最少按键数，处理下一个字符时做一次多源 Dijkstra（边权均为 1）。
// 3. 所有目标字符格子都出堆后即可停止，新状态为这些格子的距离加一次选择键。
// 复杂度：O(|S| * rc log(rc)) 时间 / O(rc) 空间
// 易错点：文本最后还要打印一个换行，等价于在末尾追加一个星号字符，别漏掉这次选择。
// 易错点：方向键跳的是「第一个不同字符」，相同字符要整段跳过，只移动一格会算出偏大的答案。
#include <bits/stdc++.h>
using namespace std;
int main(){
    int r, c;
    if(!(cin >> r >> c)) return 0;
    vector<string> key(r);
    for(int i = 0; i < r; i++){
        string s;
        cin >> s;
        for(char ch : s){
            if(ch != '\\') key[i] += ch;
        }
    }
    c = (int)key[0].size();
    string text;
    cin >> text;
    text += "*";
    int dr[4] = {-1, 1, 0, 0};
    int dc[4] = {0, 0, -1, 1};
    int V = r * c;
    vector<array<int, 4>> jump(V);
    for(int i = 0; i < r; i++){
        for(int j = 0; j < c; j++){
            int id = i * c + j;
            for(int k = 0; k < 4; k++){
                int x = i + dr[k], y = j + dc[k];
                while(x >= 0 && x < r && y >= 0 && y < c && key[x][y] == key[i][j]){
                    x += dr[k];
                    y += dc[k];
                }
                jump[id][k] = (x >= 0 && x < r && y >= 0 && y < c) ? x * c + y : id;
            }
        }
    }
    const int INF = 1e9;
    vector<int> cur(V, INF);
    cur[0] = 0;
    for(char ch : text){
        vector<int> dist = cur;
        priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;
        int need = 0;
        for(int p = 0; p < V; p++){
            if(dist[p] < INF) pq.push({dist[p], p});
            if(key[p / c][p % c] == ch) need++;
        }
        int settled = 0;
        while(!pq.empty()){
            int d = pq.top().first;
            int p = pq.top().second;
            pq.pop();
            if(d != dist[p]) continue;
            if(key[p / c][p % c] == ch && ++settled == need) break;
            for(int k = 0; k < 4; k++){
                int q = jump[p][k];
                if(d + 1 < dist[q]){
                    dist[q] = d + 1;
                    pq.push({dist[q], q});
                }
            }
        }
        vector<int> nxt(V, INF);
        for(int p = 0; p < V; p++){
            if(key[p / c][p % c] == ch && dist[p] < INF) nxt[p] = dist[p] + 1;
        }
        cur = nxt;
    }
    cout << *min_element(cur.begin(), cur.end()) << "\n";
    return 0;
}
Keyboarding

正文

一本通·提高篇的其它内容
