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

动态WA · 2020-03-14 21:56:51 · 题解

老师说这道题直接搜会TLE的，我冒着风险试了试，居然A了(其实是有优化啦)

优化不会太难，请放心食用，只是数位的转换可能有会晕眩效果

主要思路:用int型存储状态，状态有密码值和光标位置两个参数，再用bool数组判重

缺点：数位交换的代码写得我要炸，用数组的话直接swap就完事了

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<queue>
using namespace std;
struct node{
    int num,line,step;
};
bool c[1000000][7];
queue<node> q;
int a,b;
int main(){
    cin>>a>>b;
    node dw;
    dw.num=a;
    dw.line=1;
    dw.step=0;
    q.push(dw);
    c[dw.num][dw.line]=1;
    while (!q.empty()){
        node d=q.front();
        q.pop();
        if (d.num==b){
            cout<<d.step;
            return 0;
        }
        d.step++;
        node r;
        if (d.line>1){
            r=d;
            r.line--;//光标左拉
            if (!c[r.num][r.line]){
                q.push(r);
                c[r.num][r.line]=1;
            }
            r.line++;
            int gao=r.num/100000;
            int wei=1;
            for (int i=1;i<=6-r.line;i++)
                wei*=10;
            int di=r.num/wei%10;
            r.num%=100000;
            r.num+=100000*di;
            r.num=r.num-di*wei+gao*wei;//1和当前位交换
            if (!c[r.num][r.line]){
                q.push(r);
                c[r.num][r.line]=1;
            }
        }
        if (d.line<6){
            r=d;
            r.line++;//光标右拉
            if (!c[r.num][r.line]){
                q.push(r);
                c[r.num][r.line]=1;
            }
            r.line--;
            int di=r.num%10;
            int wei=1;
            for (int i=1;i<=6-r.line;i++)
                wei*=10;
            int gao=r.num/wei%10;
            r.num=r.num-di+gao;
            r.num=r.num-gao*wei+di*wei;//6和当前位交换
            if (!c[r.num][r.line]){
                q.push(r);
                c[r.num][r.line]=1;
            }
        }
        r=d;
        int wei=1;
        for (int i=1;i<=6-r.line;i++)
            wei*=10;
        if (r.num/wei%10<9){
            r.num+=wei;//当前位加1
            if (!c[r.num][r.line]){
                q.push(r);
                c[r.num][r.line]=1;
            }
            r.num-=wei;
        }
        if (r.num/wei%10>0){
            r.num-=wei;//当前位减1
            if (!c[r.num][r.line]){
                q.push(r);
                c[r.num][r.line]=1;
            }
            r.num+=wei;
        }
    }
} 

写这种代码的感觉跟在画几条辅助线后找全等三角形的感觉是一样的