A1189 [NOI2001] 聪明的打字员

#include <bits/stdc++.h>
using namespace std;

// 6 位密码 + 光标位置的状态空间：10^6 * 6 = 6*10^6。
// 状态编码：num * 6 + cur，dist 存最少按键次数。
const int NUM = 1000000;
const int CUR = 6;

int digitsOf(int num, int pos) {
    // 位置从左到右 0..5
    int div = 1;
    for (int i = 0; i < 5 - pos; i++) div *= 10;
    return num / div % 10;
}

int setDigit(int num, int pos, int d) {
    int div = 1;
    for (int i = 0; i < 5 - pos; i++) div *= 10;
    int old = num / div % 10;
    return num + (d - old) * div;
}

int main() {
    int s, t;
    cin >> s >> t;

    const int ST = NUM * CUR;
    vector<int> dist(ST, -1);
    vector<int> que(ST);
    int head = 0, tail = 0;

    dist[s * CUR + 0] = 0;
    que[tail++] = s * CUR + 0;

    int answer = -1;
    while (head < tail) {
        int st = que[head++];
        int num = st / CUR;
        int cur = st % CUR;
        int d = dist[st];
        if (num == t) {
            answer = d;
            break;
        }
        int cd = digitsOf(num, cur);
        // 六个键：swap0, swap1, up, down, left, right
        int cand[6];
        // swap0：与 1 号位置交换
        if (cur != 0) {
            int d0 = digitsOf(num, 0);
            cand[0] = setDigit(setDigit(num, cur, d0), 0, cd);
        } else cand[0] = num;
        // swap1：与 6 号位置交换
        if (cur != 5) {
            int d5 = digitsOf(num, 5);
            cand[1] = setDigit(setDigit(num, cur, d5), 5, cd);
        } else cand[1] = num;
        // up：当前位 +1
        cand[2] = (cd < 9) ? setDigit(num, cur, cd + 1) : num;
        // down：当前位 -1
        cand[3] = (cd > 0) ? setDigit(num, cur, cd - 1) : num;
        // left / right：移动光标
        cand[4] = num;
        cand[5] = num;
        int ncur[6] = {cur, cur, cur, cur, cur - 1, cur + 1};
        for (int k = 0; k < 6; k++) {
            if (ncur[k] < 0 || ncur[k] >= CUR) continue;
            int nst = cand[k] * CUR + ncur[k];
            if (dist[nst] != -1) continue;
            dist[nst] = d + 1;
            que[tail++] = nst;
        }
    }

    cout << answer << "\n";
    return 0;
}