poj 1184 聪明的打字员

阿兰是某机密部门的打字员，她现在接到一个任务：需要在一天之内输入几百个长度固定为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号位置上。当巧妙地使用上述六个特殊键之后，可以得到目标密码，这时光标允许停在任何一个位置。

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

Input

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

Output

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

Sample Input
123456 654321
Sample Output
11

解答

题意：用最少的操作次数转换给定序列到目标序列。

六种操作：

• 左移和右移：将光标位置左移一位或右移一位，在第一位时无法左移，最后一位时无法右移。
• 左交换和右交换：将光标位置的数字与第一位或最后一位交换
• 增大和减小：将光标位置的数字增大或减小1

技巧：有6位，同一个数每位只会执行一次，所以状态表示某一维度为6。因为Bfs的特点是会把所有操作可能都入队，所以再次来到这个数的这个位时，已然是做了所有能做的功夫了。

#include<cstdio>
#include<cstring>
#include<queue>
#include<algorithm>

using namespace std;

int pos[6]={100000,10000,1000,100,10,1};//进制
bool v[1000005][6];//某数某位是否操作过
int target,tar[6];//target目标数组，tar辅助输入
struct node
{
    int num;
    int cursor;//在哪位操作
    int step;//操作数量
    node(int n,int c,int s):num(n),cursor(c),step(s){}
};
node n(0,0,0);//起始状态

int swap(int num,int p1,int p2)//交换num的p1和p2位
{
    int v1=(num/pos[p1])%10;//找出p1位
    int v2=(num/pos[p2])%10;
    num += (v2-v1)*pos[p1];//p1的新变化
    num += (v1-v2)*pos[p2];
    return num;
}

int up(int num,int p)//增加num的p位
{
    return num+pos[p];
}

int down(int num,int p)
{
    return num-pos[p];
}

int bfs()
{
    memset(v,false,sizeof(v));
    queue<node> q;
    q.push(n);
    while(!q.empty())
    {
        node t=q.front();q.pop();
        int num=t.num,cursor=t.cursor,step=t.step;
        if(num==target) return step;
        step++;
        //两种交换操作
        if(cursor!=0)
        {
            int temp=swap(num,0,cursor);
            if(!v[temp][cursor])
            {
                q.push({temp,cursor,step});
                v[temp][cursor]=true;
            }
        }
        if(cursor!=5)
        {
            int temp=swap(num,5,cursor);
            if(!v[temp][cursor])
            {
                q.push({temp,cursor,step});
                v[temp][cursor]=true;
            }
        }
        int val=(num/pos[cursor])%10;//当前位值
        //增加和减少
        if(val !=9 && val!=tar[cursor])
        {
            int temp=up(num,cursor);
            if(!v[temp][cursor])
            {
                q.push({temp,cursor,step});
                v[temp][cursor]=true;
            }
        }
        if(val!=0&&val!=tar[cursor])
        {
            int temp=down(num,cursor);
            if(!v[temp][cursor])
            {
                q.push({temp,cursor,step});
                v[temp][cursor]=true;
            }
        }
        //左移右移,交换的时候特判了0和5,这里要考虑进来
        if(cursor!=0&&(val==tar[cursor]||cursor==5))
        {
            if(!v[num][cursor-1])
            {
                q.push({num,cursor-1,step});
                v[num][cursor-1]=true;
            }
        }
        if(cursor!=5&&(val==tar[cursor]||cursor==0))
        {
            if(!v[num][cursor+1])
            {
                q.push({num,cursor+1,step});
                v[num][cursor+1]=true;
            }
        }
    }
    return -1;
}

int main()
{
    char a[10],b[10];
    scanf("%s %s",a,b);
    for(int i=0;i<6;i++)
    {
        tar[i]=a[i]-'0';
        n.num += tar[i]*pos[i];
    }
    for(int i=0;i<6;i++)
    {
        tar[i]=b[i]-'0';
        target += tar[i]*pos[i];
    }
    printf("%d\n",bfs());
}