Skip to content

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

11

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;
}