🔗 UVA-1714 Keyboarding

tags: `BFS` `最短路徑(Shortest Path)`

C++ 範例程式碼已於 UVA、瘋狂程設(CPE) 上測試通過。

題意

給定一個大小為 $r \times c$ 的 虛擬鍵盤，以及一個指定字串 $s$ ，請求出在虛擬鍵盤上輸入指定字串所需的最少按鍵次數。

虛擬鍵盤由一個矩形網格組成，每個格子可能包含大寫字母、數字、橫線或星號（代表 Enter 鍵）。鍵盤上的每個字元都代表一個鍵，並且可能由多個連接的單元格組成。使用者可以透過五個按鈕控制一個 游標(cursor) 在鍵盤上移動和選擇字元，包括四個方向鍵和一個選擇鍵。

每次按方向鍵時，游標會跳到 與當前位置不同的下一個字元 。如果不存在這樣的字元，則游標不會移動。每次按選擇鍵時，游標所在位置的字元將被打印出來。

輸出給定字串 $s$ 所需的最少按鍵次數。

注意，在輸出完指定字串後，還需要將游標移動到 Enter 鍵(星號) 的位置，並按下 Enter 鍵。

思路：BFS

根據題意，每次游標移動時，都會跳到 與當前位置不同的下一個字元 。因此，我們可以透過往四個方向尋找下一個與當前按鍵不同的按鍵預處理出每個位置能夠移動到的位置。令 $nxt[x][y]$ 表示在位置 $(x, y)$ 時，能夠移動到的位置。

由於在輸入完指定字串 $s$ 後，還需要將游標移動到 Enter 鍵(星號) 的位置，並按下 Enter 鍵，因此，可以直接在 $s$ 的最後加上一個星號。

接著，我們可以透過 BFS 來求解答案。我們可以使用一個佇列(Queue) $q$ 來存儲當前的狀態，並透過一個陣列 $\text{visited}$ 來記錄走到 $(x, y)$ 時，已經找到的字元數最多是多少，方便後續剪枝(pruning) 。

每個節點紀錄目前的位置 $(x, y)$ 、當前正在嘗試輸入的字串索引 $idx$ 、以及到達該位置的按鍵次數 $step$ 。
從鍵盤的左上角 $(0, 0)$ 開始，嘗試按順序輸入字串中的每一個字元。
對每一個位置，如果該位置的字符與目標字符相符，則檢查是否已經輸入完畢。
- 如果還未完畢，則將遊標保持在當前位置，按下選擇鍵，並將下一個字符的索引加入佇列繼續處理。
- 當 BFS 處理到字串末尾的 Enter 鍵時，再按下選擇鍵，即可得到答案。
如果當前位置的字符不符，則遍歷所有預計算的下一個可到達的不同按鍵位置，並更新 BFS 的佇列。
- 若此時下一個可到達位置 $(nx, ny)$ 已經找到的字元數比當前多，則存在更優的解，因此可以對其剪枝(pruning) 。

複雜度分析

時間複雜度： $\mathcal{O}(rcn)$ ，其中 $r$ 和 $c$ 分別為虛擬鍵盤的行數和列數， $n$ 為目標字串的長度。在最壞情況下，每個按鍵都需要嘗試 $n$ 次，因此總時間複雜度為 $\mathcal{O}(rcn)$ 。
空間複雜度： $\mathcal{O}(rcn)$ $O (rc n)$ 。
- 需要預處理每個位置的下一個不同按鍵位置，空間複雜度為 $\mathcal{O}(rc)$ 。
- 佇列的大小最多可能達到 $rcn$ ，因此空間複雜度也是 $\mathcal{O}(rcn)$ 。

Python 範例程式碼僅能在 瘋狂程設(CPE) 上通過，UVA 上會 TLE 。

from collections import deque

import sys
def input(): return sys.stdin.readline().strip()
def print(val=""): sys.stdout.write(str(val) + '\n')

def to_int(s: str) -> int:
    if s.isdigit():
        return int(s)
    elif s.isalpha():
        return ord(s) - ord('A') + 10
    elif s == '-':
        return 36
    else: # s == '*', enter
        return 37
    
while True:
    try:
        r, c = map(int, input().split())
    except:
        break
    kb = [[to_int(ch) for ch in input()] for _ in range(r)]
    s = [to_int(ch) for ch in input()] + [37] # 最後需要 Enter 鍵
    # 預處理下一個與當前按鍵不同的按鍵
    nxt = [[[] for j in range(c)] for i in range(r)]
    for x in range(r):
        for y in range(c):
            for dx, dy in ((1, 0), (-1, 0), (0, 1), (0, -1)):
                nx, ny = x + dx, y + dy
                while 0 <= nx < r and 0 <= ny < c and kb[nx][ny] == kb[x][y]:
                    nx, ny = nx + dx, ny + dy
                if 0 <= nx < r and 0 <= ny < c:
                    nxt[x][y].append((nx, ny))
    # BFS
    ans = float("inf")
    q = deque([(0, 0, 0, 0)])
    visited = [[-1] * c for _ in range(r)] # 走到 (x, y) 時，已經找到的字元數是多少
    while q:
        x, y, idx, step = q.popleft()
        if kb[x][y] == s[idx]: # 當前按鍵與目標字元相同
            if idx == len(s) - 1: # 找到答案
                ans = step + 1
                break
            q.append((x, y, idx+1, step+1)) # 按下當前按鍵，找下一個字元
            visited[x][y] = max(visited[x][y], idx+1)
        else:
            for nx, ny in nxt[x][y]:
                if visited[nx][ny] >= idx: # 剪枝，到達 (nx, ny) 時已經找到的字元數比當前多
                    continue
                visited[nx][ny] = idx
                q.append((nx, ny, idx, step+1)) # 移動到 (nx, ny)
    print(ans)

#include <bits/stdc++.h>
using namespace std;
const int N = 55;
#define endl '\n'

struct Node {
    int x, y, idx, step;
};

int main() {
    ios::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr);
    int r, c, x, y, nx, ny, idx, step;
    vector<pair<int, int>> nxt[N][N];
    int visited[N][N];
    int DX[4] = {1, -1, 0, 0}, DY[4] = {0, 0, 1, -1};
    while (cin >> r >> c){
        vector<string> kb(r);
        for (int i = 0; i < r; i++){
            cin >> kb[i];
        }
        string s;
        cin >> s;
        s += "*"; // add end mark (enter)
        // find next key that is different from current key
        for (int i = 0; i < r; i++){
            for (int j = 0; j < c; j++){
                nxt[i][j].clear();
                for (int k = 0; k < 4; k++){
                    nx = i + DX[k], ny = j + DY[k];
                    while (nx >= 0 && nx < r && ny >= 0 && ny < c && kb[nx][ny] == kb[i][j]){
                        nx += DX[k], ny += DY[k];
                    }
                    if (nx >= 0 && nx < r && ny >= 0 && ny < c){ // valid
                        nxt[i][j].push_back({nx, ny});
                    }
                }
            }
        }
        // BFS
        int ans = INT_MAX;
        // visited[i][j] = k means that when we reach (i, j), we have at most input s[k]
        memset(visited, -1, sizeof(visited));
        queue<Node> q;
        q.push({0, 0, 0, 0}); // (x, y, idx, step)
        while (!q.empty()){
            Node node = q.front(); q.pop();
            x = node.x, y = node.y, idx = node.idx, step = node.step;
            if (kb[x][y] == s[idx]){
                if (idx == s.size() - 1){ // reach the end
                    ans = step + 1;
                    break;
                }
                q.push({x, y, idx+1, step+1}); // stay at current position, but press the botton
                visited[x][y] = max(visited[x][y], idx+1); // update visited
            } else {
                for (pair<int, int> p : nxt[x][y]){
                    nx = p.first, ny = p.second;
                    if (visited[nx][ny] >= idx){ // Pruning
                        continue;
                    }
                    visited[nx][ny] = idx;
                    q.push({nx, ny, idx, step+1}); // move to next position
                }
            }
        }
        cout << ans << endl;
    }
    return 0;
}