11125: 【原1125】Typist

题目

题目描述

author: Minshen Zhu 原OJ链接：https://acm.sjtu.edu.cn/OnlineJudge-old/problem/1125

Description

宽神的键盘上只有6个按键，我们可以分别记为key1, key2, ... , key6。

宽神输入的时候，录入区会出现一个随机的六位数和一个输入光标。初始的输入光标指向第一位数字。这时候宽神将巧妙利用他的6个按键将初始数字变为他要输入的目标数字。

下面列出每个键的作用：

key1：按key1，光标位置不变，将光标所在位置的数字与录入区的1号位置的数字（左起第一个数字）交换。如果光标已经处在录入区的1号位置，则按key1键之后，录入区的数字不变；

key2：按key2，光标位置不变，将光标所在位置的数字与录入区的6号位置的数字（左起第六个数字）交换。如果光标已经处在录入区的6号位置，则按key2键之后，录入区的数字不变；

key3：按key3，光标位置不变，将光标所在位置的数字加1（除非该数字是9）。例如，如果光标所在位置的数字为2，按key3之后，该处的数字变为3；如果该处数字为9，则按key3之后，数字不变，光标位置也不变；

key4：按key4，光标位置不变，将光标所在位置的数字减1（除非该数字是0），如果该处数字为0，则按key4之后，数字不变，光标位置也不变；

key5：按key5，光标左移一个位置，如果光标已经在录入区的1号位置（左起第一个位置）上，则光标不动；

key6：按key6，光标右移一个位置，如果光标已经在录入区的6号位置（左起第六个位置）上，则光标不动。

现在宽神想知道，他输入一个数字最少需要击键多少次。

Input Format

共两行，每行各含一个长度为6的数，前者为初始数字，后者为目标数字。

Output Format

仅一行，含有一个正整数，为最少需要的击键次数。

Sample Input

123456
654321

Sample Output

FineArtz's solution

/* typist */
#include <iostream>
#include <cstring>
#include <cmath>
using namespace std;

const int FACT[6] = {100000, 10000, 1000, 100, 10, 1};
const int MAXS = 2000000;

struct String{
    int s = 0, cursor = 0;
    long long step = 0;

    String() = default;

    String(const String &ss){
        s = ss.s;
        step = ss.step;
        cursor = ss.cursor;
    }

    String &operator =(const String &ss){
        s = ss.s;
        step = ss.step;
        cursor = ss.cursor;
        return *this;
    }

    bool operator ==(const String &ss){
        return s == ss.s;
    }

    const int operator [](int x) const {
        return s / FACT[x] % 10;
    }

    void inc(int x){
        s += FACT[x];
    }
    void dec(int x){
        s -= FACT[x];
    }

    void swap(int x, int y){
        int p = s / FACT[x] % 10, q = s / FACT[y] % 10;
        s += (q - p) * FACT[x];
        s += (p - q) * FACT[y];
    }
};

String s, a;
String q[2000005];
bool v[1000000][7] = {0};
int front = 0, rear = 0;

void push(const String &n){
    if (v[n.s][n.cursor])
        return;
    rear = (rear + 1) % MAXS;
    q[rear] = n;
    v[n.s][n.cursor] = true;
}

long long bfs(){
    push(s);
    while (front != rear){
        front = (front + 1) % MAXS;
        String t = q[front];
        if (t == a){
            return t.step;
        }
        String n;
        int i = t.cursor;
        if (i != 0){
            n = t;
            ++n.step;
            n.swap(i, 0);
            push(n);
        }
        if (i != 5){
            n = t;
            ++n.step;
            n.swap(i, 5);
            push(n);
        }
        if (t[i] != a[i]){
            if (t[i] != 0){
                n = t;
                ++n.step;
                n.dec(i);
                push(n);
            }
            if (t[i] != 9){
                n = t;
                ++n.step;
                n.inc(i);
                push(n);
            }
        }
        if (i != 0){
            n = t;
            ++n.step;
            --n.cursor;
            push(n);
        }
        if (i != 5){
            n = t;
            ++n.step;
            ++n.cursor;
            push(n);
        }
    }
    return -1;
}

int main(){
    char p[7], q[7];
    cin >> p >> q;
    for (int i = 0; i < 6; ++i){
        s.s = s.s * 10 + p[i] - '0';
        a.s = a.s * 10 + q[i] - '0';
    }
    long long ans = bfs();
    cout << ans << endl;
    return 0;
}