题解 P1949 【聪明的打字员_NOI导刊2011提高（10）】

题目描述

阿兰是某机密部门的打字员，她现在接到一个任务：需要在一天之内输入几百个长度固定为6的密码。当然，她希望输入的过程中敲击键盘的总次数越少越好。

不幸的是，出于保密的需要，该部门用于输入密码的键盘是特殊设计的，键盘上没有数字键，而只有以下六个键：swap0,swap1,up,down,left,right。为了说明这6个键的作用，我们先定义录入区的6个位置的编号，从左至右依次为1,2,3,4,5,6。下面列出每个键的作用：

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

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

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

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

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

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

当然，为了使这样的键盘发挥作用，每次录入密码之前，录入区总会随机出现一个长度为6的初始密码，而且光标会固定出现在1号位置上。当巧妙的使用上述六个特殊键之后，可以得到目标密码，这时光标允许停留在任何一个位置。

现在，阿兰需要你的帮助，编写一个程序，求出录入一个密码需要的最少的击键次数。

输入输出格式

输入格式：

仅一行，含有两个长度为6的数，前者为初始密码，后者为目标密码，两个密码之间用一个空格隔开。

输出格式：

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

输入输出样例

输入样例#1：

123456 654321

输出样例#1：

11

主要思路：BFS + 循环队列

这个题的数只有6位，我们直接当六位数存不就好了

首先不能写DFS，明显这题BFS要比DFS更优（DFS不就退化成了穷举吗（大雾））

swap0，swap1，up，down操作，直接模拟就好，left和right就更好办了，直接更新光标左右就好。

code#1:36分（肯定TLE了）

福利：自带野生debug代码

#include<iostream>
#include<cstdio>
#include<cmath>
#include<algorithm>
#include<queue>
using namespace std;
#define go(i,j,n,k) for(int i=j;i<=n;i+=k)
#define fo(i,j,n,k) for(int i=j;i>=n;i-=k)
inline ll read(){
    ll x=0,f=1;char ch=getchar();
    while(ch>'9'||ch<'0'){if(ch=='-')f=-f;ch=getchar();}
    while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
    return x*f;
}
inline void fre() {
    freopen(".in", "r", stdin);
    freopen(".out", "w", stdout);
}
int st, ed;
int vis[1000100][7]; // 判重数组

inline int swap0(int x, int now) {
    int res = 1;
    now = 6 - now + 1;
    go(i, 1, now - 1, 1) res *= 10;
    int xx = (x / res) % 10;
    int yy = (x / 100000);
    int ans = x;
    ans -= xx * res;
    ans -= yy * 100000;
    ans += xx * 100000;
    ans += yy * res;
    return ans;
}
inline int swap1(int x, int now) {
    int res = 1;
    now = 6 - now + 1;
    go(i, 1, now - 1, 1) res *= 10;
    int xx = (x / res) % 10;
    int yy = x % 10;
    int ans = x;
    ans -= xx * res;
    ans -= yy;
    ans += xx;
    ans += yy * res;
    return ans;
}
inline int up(int x, int now) {
    int res = 1;
    now = 6 - now + 1;
    go(i, 1, now - 1, 1) res *= 10;
    int ju = (x / res) % 10;
    if(ju == 9) return x;
    return x + res;
}
inline int down(int x, int now) {
    int res = 1;
    now = 6 - now + 1;
    go(i, 1, now - 1, 1) res *= 10;
    int ju = (x / res) % 10;
    if(ju == 0) return x;
    return x - res;
}
// 四种操作
inline void debug() {
    puts("debug模式：");
    puts("1.swap0  2.swap1");
    puts("3.up     4.down");
    int s = read(), st = read(), now = read();
    if(s == 1) {
        cout << swap0(st, now) << "\n";
    } else if(s == 2) {
        cout << swap1(st, now) << "\n";
    } else if(s == 3) {
        cout << up(st, now) << "\n";
    } else if(s == 4) {
        cout << down(st, now) << "\n";
    }
}

struct node{
    int x, now, dep;
    node(int _x = 0, int _now = 0, int _dep = 0) : x(_x), now(_now), dep(_dep) {}
    node() : node(0, 0, 0) {}
};
queue<node> q;
inline int bfs(int st, int ed) {
    q.push(node(st, 1, 0));
    while(!q.empty()) {
        node get = q.front(); q.pop();
        int oo, x = get.x, now = get.now, deep = get.dep;
        vis[x][now] = 1;
        if(x == ed)
            return deep;
        oo = swap0(x, now);
        if(!vis[oo][now]) q.push(node(oo, now, deep + 1));
        oo = swap1(x, now);
        if(!vis[oo][now]) q.push(node(oo, now, deep + 1));
        oo = up(x, now);
        if(!vis[oo][now]) q.push(node(oo, now, deep + 1));
        oo = down(x, now);
        if(!vis[oo][now]) q.push(node(oo, now, deep + 1));
        if(now > 1 && !vis[x][now - 1]) q.push(node(x, now - 1, deep + 1)); // 注意这里的特判！now不能越界！
        if(now < 6 && !vis[x][now + 1]) q.push(node(x, now + 1, deep + 1)); // 注意这里的特判！now不能越界！
    }
}

int main(){
    //fre();
    // while(1) 
    //	debug();
    st = read(), ed = read();
    if(st == ed) {
        cout << "0\n";
        return 0;
    }
    cout << bfs(st, ed) << "\n";
    return 0;
}

为什么会TLE？

首先，尽管我们在入队之前就已经判重了，但是这个代码会重复插一样的点，所以我们可以在从队列中取出时来再次判重。

而且，众所周知，有种说法说STL很慢，所以我好奇的自己手写了个队列。

code#2:72分（这次WA了）

#include<iostream>
#include<cstdio>
#include<cmath>
#include<algorithm>
using namespace std;
#define go(i,j,n,k) for(int i=j;i<=n;i+=k)
#define fo(i,j,n,k) for(int i=j;i>=n;i-=k)
#define mn 10000100
inline ll read(){
    ll x=0,f=1;char ch=getchar();
    while(ch>'9'||ch<'0'){if(ch=='-')f=-f;ch=getchar();}
    while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
    return x*f;
}
inline void fre() {
    freopen(".in", "r", stdin);
    freopen(".out", "w", stdout);
}
int st, ed;
bool vis[1000100][7]; // 判重数组 
int ans = inf;
int ress[7] = {0, 1, 10, 100, 1000, 10000, 100000};

inline int swap0(int x, int now) {
    now = 6 - now + 1;
    int res = ress[now];
    int xx = (x / res) % 10;
    int yy = (x / 100000);
    int ans = x;
    ans -= xx * res;
    ans -= yy * 100000;
    ans += xx * 100000;
    ans += yy * res;
    return ans;
}
inline int swap1(int x, int now) {
    now = 6 - now + 1;
    int res = ress[now];
    int xx = (x / res) % 10;
    int yy = x % 10;
    int ans = x;
    ans -= xx * res;
    ans -= yy;
    ans += xx;
    ans += yy * res;
    return ans;
}
inline int up(int x, int now) {
    now = 6 - now + 1;
    int res = ress[now];
    int ju = (x / res) % 10;
    if(ju == 9) return x;
    return x + res;
}
inline int down(int x, int now) {
    now = 6 - now + 1;
    int res = ress[now];
    int ju = (x / res) % 10;
    if(ju == 0) return x;
    return x - res;
}

inline void debug() {
    puts("debug模式：");
    puts("1.swap0  2.swap1");
    puts("3.up     4.down");
    int s = read(), st = read(), now = read();
    if(s == 1) {
        cout << swap0(st, now) << "\n";
    } else if(s == 2) {
        cout << swap1(st, now) << "\n";
    } else if(s == 3) {
        cout << up(st, now) << "\n";
    } else if(s == 4) {
        cout << down(st, now) << "\n";
    }
}
// 手写队列哦QwQ
int X[mn], Now[mn], dep[mn], head = 1, tail = 0;
int x, now, oo, deep;
inline int bfs(int st, int ed) {
    ++tail, X[tail] = st, Now[tail] = 1, dep[tail] = 0;
    while(head <= tail) {
        x = X[head], now = Now[head], deep = dep[head]; head++;
        // cout << x << " " << now << " " << deep << "\n";
        if(vis[x][now]) continue; // 调用前再次判重
        vis[x][now] = 1;
        if(x == ed) return deep;
        oo = swap0(x, now);
        if(!vis[oo][now]) ++tail, X[tail] = oo, Now[tail] = now, dep[tail] = deep + 1;
        oo = swap1(x, now);
        if(!vis[oo][now]) ++tail, X[tail] = oo, Now[tail] = now, dep[tail] = deep + 1;
        oo = up(x, now);
        if(!vis[oo][now]) ++tail, X[tail] = oo, Now[tail] = now, dep[tail] = deep + 1;
        oo = down(x, now);
        if(!vis[oo][now]) ++tail, X[tail] = oo, Now[tail] = now, dep[tail] = deep + 1;
        if(now > 1 && !vis[x][now - 1]) ++tail, X[tail] = x, Now[tail] = now - 1, dep[tail] = deep + 1;
        if(now < 6 && !vis[x][now + 1]) ++tail, X[tail] = x, Now[tail] = now + 1, dep[tail] = deep + 1;
    }
    return deep + 1;
}
int main(){
    st = read(), ed = read();
    if(st == ed) {
        cout << "0\n";
        return 0;
    }
    cout << bfs(st, ed) << "\n";
    return 0;
}

怎么还不AC

我们可以试着把数组开大点，咦？多了9分？

好像是数组大小？？但是我的空间已经开到最大了啊

这个时候就可以用循环队列卡空间了

具体写法看代码

code#3:100分

#include<iostream>
#include<cstdio>
#include<cmath>
#include<algorithm>
using namespace std;
#define go(i,j,n,k) for(int i=j;i<=n;i+=k)
#define fo(i,j,n,k) for(int i=j;i>=n;i-=k)
#define mn 10000100
inline ll read(){
    ll x=0,f=1;char ch=getchar();
    while(ch>'9'||ch<'0'){if(ch=='-')f=-f;ch=getchar();}
    while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
    return x*f;
}
inline void fre() {
    freopen(".in", "r", stdin);
    freopen(".out", "w", stdout);
}
int st, ed;
bool vis[1000100][7]; // 判重数组 
int ress[7] = {0, 1, 10, 100, 1000, 10000, 100000};
int res, xx, yy, ans, ju;
inline int swap0(int x, int now) {
    now = 6 - now + 1;
    res = ress[now];
    xx = (x / res) % 10;
    yy = (x / 100000);
    ans = x;
    ans -= xx * res;
    ans -= yy * 100000;
    ans += xx * 100000;
    ans += yy * res;
    return ans;
}
inline int swap1(int x, int now) {
    now = 6 - now + 1;
    res = ress[now];
    xx = (x / res) % 10;
    yy = x % 10;
    ans = x;
    ans -= xx * res;
    ans -= yy;
    ans += xx;
    ans += yy * res;
    return ans;
}
inline int up(int x, int now) {
    now = 6 - now + 1;
    res = ress[now];
    ju = (x / res) % 10;
    if(ju == 9) return x;
    return x + res;
}
inline int down(int x, int now) {
    now = 6 - now + 1;
    res = ress[now];
    ju = (x / res) % 10;
    if(ju == 0) return x;
    return x - res;
}

inline void debug() {
    puts("debug模式：");
    puts("1.swap0  2.swap1");
    puts("3.up     4.down");
    int s = read(), st = read(), now = read();
    if(s == 1) {
        cout << swap0(st, now) << "\n";
    } else if(s == 2) {
        cout << swap1(st, now) << "\n";
    } else if(s == 3) {
        cout << up(st, now) << "\n";
    } else if(s == 4) {
        cout << down(st, now) << "\n";
    }
}

int X[mn], Now[mn], dep[mn], head = 0, tail = 0;
int x, now, oo, deep;
inline int bfs(int st, int ed) {
    ++tail, X[tail] = st, Now[tail] = 1, dep[tail] = 0;
    while(head != tail) { // 这里就不能是head <= tail了
        ++head;
        if(head > 10000000) head = 0; // 记得循环
        x = X[head], now = Now[head], deep = dep[head]; 
        // cout << x << " " << now << " " << deep << "\n";
        if(x == ed) return deep;
        if(vis[x][now]) continue;
        vis[x][now] = 1;
        oo = swap0(x, now);
        if(!vis[oo][now]) {   // 都要循环的QAQ
            if(++tail > 10000000) tail = 0;
            X[tail] = oo, Now[tail] = now, dep[tail] = deep + 1;
        }
        oo = swap1(x, now);
        if(!vis[oo][now]) {
            if(++tail > 10000000) tail = 0;
            X[tail] = oo, Now[tail] = now, dep[tail] = deep + 1;
        }
        oo = up(x, now);
        if(!vis[oo][now]) {
            if(++tail > 10000000) tail = 0;
            X[tail] = oo, Now[tail] = now, dep[tail] = deep + 1;
        }
        oo = down(x, now);
        if(!vis[oo][now]) {
            if(++tail > 10000000) tail = 0;
            X[tail] = oo, Now[tail] = now, dep[tail] = deep + 1;
        }
        if(now > 1 && !vis[x][now - 1]) {
            if(++tail > 10000000) tail = 0; 
            X[tail] = x, Now[tail] = now - 1, dep[tail] = deep + 1;
        }
        if(now < 6 && !vis[x][now + 1]) {
            if(++tail > 10000000) tail = 0; 
            X[tail] = x, Now[tail] = now + 1, dep[tail] = deep + 1;
        }
    }
    return deep + 1;
}

int main(){
    st = read(), ed = read();
    if(st == ed) {
        cout << "0\n";
        return 0;
    }
    cout << bfs(st, ed) << "\n";
    return 0;
}

希望可以帮到被卡空间的同学