poj1184 聪明的打字员
L - 聪明的打字员
Time Limit:1000MS Memory Limit:65536KB 64bit IO Format:%I64d & %I64u
Submit StatusDescription
阿兰是某机密部门的打字员，她现在接到一个任务：需要在一天之内输入几百个长度固定为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 654321Sample Output
11搜索的壮态压缩，其实，左移是没什么用的，因为，你大可右移，在右移的时候，就把数值改变了去就可以，因为数值的改变和你光标所在的位置是没关的，只要，你曾移到过那个位置就可以了，所以，我们可以先把原数的所有的排列求出来，再求出排出后的数列的要移动的步数就可以了，这样我们先处理０１２３４５的所有排列，所要右移和交换的次数，对于其他的任何数，由这个数列进行相对应的变换就可以了！我们开一个visit数组前６个是６个数，最后一个是光标的壮态，我们可以发现，光标的壮态只有１０种，这样用ＢＦＳ搜索之后，只有不到２７３种壮态了，大大的压缩的，搜索的难度，时间自然就不成问题了！
#include<string.h>
#include<stdio.h>
#include<math.h>
#include<iostream>
using namespace std;
int visit[6][6][6][6][6][6][10],flag[6],maxx,aim[6],start[6];
struct tree{int pos,state,num[6],step;}queue[50000];
int sign[10][6]=//总共１０号位
{ 1,0,0,0,0,0,//0
1,1,0,0,0,0,//1
1,1,1,0,0,0,//2
1,1,1,1,0,0,//3
1,1,1,1,1,0,//4
1,1,1,1,1,1,//5
1,0,0,0,0,1,//6
1,1,0,0,0,1,//7
1,1,1,0,0,1,//8
1,1,1,1,0,1//9
};
int findstate(int ss[])
{ int i,sum;
sum=0;
for(i=0;i<6;i++)
{ if(ss[i]!=0)
sum=sum*10+1;
else sum=sum*10;
} i=sum;
if(i==100000) return 0;
else if(i==110000) return 1;
else if(i==111000) return 2;
else if(i==111100) return 3;
else if(i==111110) return 4;
else if(i==111111) return 5;
else if(i==100001) return 6;
else if(i==110001) return 7;
else if(i==111001) return 8;
else if(i==111101) return 9;
} int changestate(int i,int state)//根据几个状态的关系，来改变
{ if(i==0)
{ if(state<=4||(state>=6&&state<=8))
return state+1; else if((state==5)||(state==9))
return 5; }
else if(i==1) {
if(state<=3)
return state+6; else if(state>=5)
return state;
else if(state==4)//4号位上交换，就成了５号位
return 5; } else if(i==2)//和第一号位交换不改变state的状态
return state; } void changnum(int i,int t,int w) {
int * p=queue[t].num,j; for(j=0;j<6;j++) {
queue[w].num[j]=*(p+j);//先把num的值改变 }
if(i==0)//只有交换才改变num 的值，只有交换不改变num的值
{ return ; } else if(i==1) {
queue[w].num[queue[w].pos]=*(p+5);
queue[w].num[5]=*(p+queue[w].pos);//五号位的和当前位的地方交换
return; } else if(i==2) {
queue[w].num[queue[w].pos]=*(p);
queue[w].num[0]=*(p+queue[w].pos);//0号位的和当前位的地方交换
return ;
} } bool visitcan ( int w) {
int * p=queue[w].num ;
return visit[*p][*(p+1)][*(p+2)][*(p+3)][*(p+4)][*(p+5)][queue[w].state];
} int changevisit(int w) { int * p=queue[w].num;
visit[*p][*(p+1)][*(p+2)][*(p+3)][*(p+4)][*(p+5)][queue[w].state]=1;
return 1;
} void bfs() { memset(visit,0,sizeof(visit));
int t,w,i,state,pos,step;
t=w=1;
queue[1].pos=0;
for(i=0;i<6;i++)
queue[1].num[i]=i;
queue[1].state=0;
queue[1].step=0;
visit[0][1][2][3][4][5][0]=1;
while(t<=w) { state=queue[t].state;
pos=queue[t].pos; step=queue[t].step;
for(i=0;i<=2;i++)//三种操作，右移交６，交１号位
{ w++;
if(i==0)//右移
{
if(queue[t].pos==5)//到过右边不能移动
{
w--; continue; }
queue[w].pos=queue[t].pos+1;//光标的位置要加一
queue[w].state=changestate(i,state);
queue[w].step=step+1;
changnum(i,t,w);//右移数值不变
if(visitcan(w)) w--;
else changevisit(w);
} else if(i==1) {
if(queue[t].pos==5)//在5号不用交换
{ w--;
continue;
}
queue[w].pos=queue[t].pos;//交换5号位的光标位置不变
queue[w].state=changestate(i,state);
queue[w].step=step+1;
changnum(i,t,w);
if(visitcan(w)) w--;
else
changevisit(w);
} else if(i==2) {
if(queue[t].pos==0)//在0号不用交换
{ w--;
continue;
} queue[w].pos=queue[t].pos;//交换０号位的光标位置不变
queue[w].state=changestate(i,state);
queue[w].step=step+1;
changnum(i,t,w);
if(visitcan(w)) w--;
else changevisit(w);
} } t++; } maxx=w;
return ;
} void init(int s,int e)//把s和e 分解开来 { int num=5;
while(s) { start[num]=s%10;
s=s/10;
num--; } num=5;
while(e) { aim[num]=e%10;
num--; e=e/10;
} return ;
} bool statecan(int ss[],int i)//注意，
不一定是要状态相等才行，只要搜索到的壮态把要改变的数的壮态可以覆盖就可以了！
{ int sss[6],j; for(j=0;j<6;j++)
{ sss[j]=sign[i][j];
if((ss[j]==1)&&(sss[j]!=1)) return false;
} return true; } int main () {
int s,e,i,k,j,minx,ans,*p,state,temp[6];
bfs();//搜索各种排列的要的步数，不用考虑输入和输出的值
while(scanf("%补充：软件开发 , C++ ,
