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("%d%d",&s,&e)!=EOF) { minx=0x4f4f4f4f;
init(s,e);//將初始位置進行變換 for(j=0;j<6;j++)
temp[j]=start[j];
for(i=1;i<=maxx;i++)//枚舉出所有的數列
{ ans=0;
p=queue[i].num;
for(j=0;j<6;j++)//每一輪flag要更新
{ flag[j]=0;
} state=0;
for(j=0;j<6;j++)
{ k=fabs(temp[*(p+j)]-aim[j]);
ans+=k;
if(k!=0)
{ flag[j]=1;
} }
state=findstate(flag);
if(statecan(flag,queue[i].state))
{ ans+=queue[i].step;
if(ans<minx) { minx=ans;
} } }
printf("%d\n",minx);
} return 0; }
