题解 P1949 【[NOI2001] 聪明的打字员】

· · 题解

本题可以采用双向BFS，别名大模拟。

原因是本题的反向搜索方式与正向相同，也就是说存在反向搜索的方式。

cqbzljsqwq 大巨佬的双向BFS强悍的八维数组状态本蒟蒻学不来QwQ

蒟蒻的当前状态就是一个六位数，直接扔到下标里面标记。

那么很明显，用六位数比用字符串做状态快了无数倍，同时也会麻烦无数倍。

比如，本人程序一直很慢的原因是：有超过两小时的时间一直认为存六位数的下标应该开1e7的数组，（10^7-999999=9000001）导致memset直接爆炸。

设计状态：

struct node{
    int now;//当前的六位数密码
    int stp;//当前所用步数
    int pos;//当前光标所在位置
    bool flag;//搜索方向，0表示正向，1表示反向
}

left/right操作好说，直接改变pos的值就行了。

但up/down和swap0/swap1是要改变now的某几位上的值，很麻烦。

我们先存储一个数从左向右每一位对应的单位：

const int ws[]={1000000,100000,10000,1000,100,10,1};
//防RE，第0位也要存

假设我们要将num在pos上的值更改为x，怎么操作呢？

我们将num拆成1~(pos-1)，pos和(pos+1)~6三部分。

第一部分和第三部分不变，将第二部分修改为x*ws[pos]就行了。

1~(pos-1)的获取方式：利用C++整除的特性，num/ws[pos-1]*ws[pos-1]就可以得到了。

(pos+1)~6的获取方式：num%ws[pos]就可以得到pos之后位数的值。

由此得出上下操作的代码：

//up or down,获取num的pos位增加chg的结果
inline int UpOrDown(int num,int pos,int chg){
    int t=num/ws[pos]%10+chg;
    //获取num的pos位变化后的结果，判断是否可以这样变化
    if(t>=0&&t<=9)
        return num/ws[pos-1]*ws[pos-1]+t*ws[pos]+num%ws[pos];
    return num;
}

以及swap操作：

//swap0 or swap1,获取num的pos位与chg位交换的结果
inline int Swap(int num,int pos,int chg){
    int bg=num/ws[pos]%10;//记录pos位本来的数值
    int ed=num/ws[chg]%10;//记录chg位本来的数值
    if(bg==ed)return num;
    num=num/ws[pos-1]*ws[pos-1]+ed*ws[pos]+num%ws[pos];//pos变为ed
    num=num/ws[chg-1]*ws[chg-1]+bg*ws[chg]+num%ws[chg];//chg变为bg
    return num;
}

然后是调到吐的双向BFS。

为了方便同时标记走没走过与所用步数，我们事先将vis数组置为-1。

完整代码：

/*
(twbfs==大模拟)==true
*/
#include<queue>
#include<cstdio>
#include<cstring>
using namespace std;
short vis[1000000][7][2];
struct node{
    int now;
    int stp,pos;
    //pos: 当前光标位置
    bool flag;
}S,B,f,tmp;
queue<node>q;
const int ws[]={1000000,100000,10000,1000,100,10,1};
inline int UpOrDown(int num,int pos,int chg){
    int t=num/ws[pos]%10+chg;
    if(t>=0&&t<=9)
        return num/ws[pos-1]*ws[pos-1]+t*ws[pos]+num%ws[pos];
    return num;
}
inline int Swap(int num,int pos,int chg){
    int bg=num/ws[pos]%10;
    int ed=num/ws[chg]%10;
    if(bg==ed)return num;
    num=num/ws[pos-1]*ws[pos-1]+ed*ws[pos]+num%ws[pos];
    num=num/ws[chg-1]*ws[chg-1]+bg*ws[chg]+num%ws[chg];
    return num;
}
int TWBFS(void){
    //TIANWEN BFS(bushi)
    while(!q.empty()){
        tmp=f=q.front();
        tmp.stp++;
        q.pop();
        if(~vis[f.now][f.pos][!f.flag])
            return f.stp+vis[f.now][f.pos][!f.flag];
        //将光标左移一位
        if(f.pos>1){
            tmp.pos=f.pos-1;
            if(vis[tmp.now][tmp.pos][tmp.flag]==-1){
                vis[tmp.now][tmp.pos][tmp.flag]=tmp.stp;
                q.push(tmp);
            }
        }
        //将光标右移一位
        if(f.pos<6){
            tmp.pos=f.pos+1;
            if(vis[tmp.now][tmp.pos][tmp.flag]==-1){
                vis[tmp.now][tmp.pos][tmp.flag]=tmp.stp;
                q.push(tmp);
            }
        }
        //记得把光标移回来，不要像本蒟蒻一样傻傻踩坑
        tmp.pos=f.pos;
        //将光标所在位置的数值增加1
        tmp.now=UpOrDown(f.now,f.pos,1);
        if(vis[tmp.now][tmp.pos][tmp.flag]==-1){
            vis[tmp.now][tmp.pos][tmp.flag]=tmp.stp;
            q.push(tmp);
        }
        //将光标所在位置的数值减少1
        tmp.now=UpOrDown(f.now,f.pos,-1);
        if(vis[tmp.now][tmp.pos][tmp.flag]==-1){
            vis[tmp.now][tmp.pos][tmp.flag]=tmp.stp;
            q.push(tmp);
        }
        //swap0
        if(f.pos!=1){
            tmp.now=Swap(f.now,f.pos,1);
            if(vis[tmp.now][tmp.pos][tmp.flag]==-1){
                vis[tmp.now][tmp.pos][tmp.flag]=tmp.stp;
                q.push(tmp);
            }
        }
        //swap1
        if(f.now!=6){
            tmp.now=Swap(f.now,f.pos,6);
            if(vis[tmp.now][tmp.pos][tmp.flag]==-1){
                vis[tmp.now][tmp.pos][tmp.flag]=tmp.stp;
                q.push(tmp);
            }
        }
    }
    return 114514;
}
int main(){
    scanf("%d%d",&S.now,&B.now);
    memset(vis,-1,sizeof(vis));
    S.pos=1;
    q.push(S);
    B.flag=1;
    vis[S.now][1][0]=0;
    //最终密码的光标在每一位都有可能出现
    for(int i=1;i<=6;++i){
        B.pos=i;
        vis[B.now][i][1]=0;
        q.push(B);
    }
    printf("%d\n",TWBFS());
    return 0;
}

end.