Problem Description
Now an emergent task for you is to open a password lock. The password is consisted of four digits. Each digit is numbered from 1 to 9.
Each time, you can add or minus 1 to any digit. When add 1 to '9', the digit will change to be '1' and when minus 1 to '1', the digit will change to be '9'. You can also exchange the digit with its neighbor. Each action will take one step.
Now your task is to use minimal steps to open the lock.
Note: The leftmost digit is not the neighbor of the rightmost digit.
Each time, you can add or minus 1 to any digit. When add 1 to '9', the digit will change to be '1' and when minus 1 to '1', the digit will change to be '9'. You can also exchange the digit with its neighbor. Each action will take one step.
Now your task is to use minimal steps to open the lock.
Note: The leftmost digit is not the neighbor of the rightmost digit.
?
?
Input
The input file begins with an integer T, indicating the number of test cases.
Each test case begins with a four digit N, indicating the initial state of the password lock. Then followed a line with anotther four dight M, indicating the password which can open the lock. There is one blank line after each test case.
Each test case begins with a four digit N, indicating the initial state of the password lock. Then followed a line with anotther four dight M, indicating the password which can open the lock. There is one blank line after each test case.
?
?
Output
For each test case, print the minimal steps in one line.
?
?
Sample Input
2 1234 2144 1111 9999
?
?
Sample Output
2 4
#include<stdio.h>
#include<string.h>
int vist[10],flog;
char str[5],ch[5];
void DFS(int j,int x,int step,char ch1[])
{
int i,st,e;
char tem[5];
//printf("%s %d\n",ch1,ste);
if(str[0]==ch1[0]&&str[1]==ch1[1]&&str[2]==ch1[2]&&str[3]==ch1[3])//一樣了
{
if(flog>step) //記錄小的
flog=ste;
//printf("%d ",ste);
}
vist[x]=1; //表示在ch1中第x位置方問(wèn)過(guò)
for(i=x+1;i<4;i++)
if(vist[i]==0)
{
if(str[j]-ch1[i]>=5||str[j]-ch1[i]<=-5)//第一步，當(dāng)成立時(shí)，把ch1[i]加或減變成str[j]的所用時(shí)間加起來(lái)，會(huì)用tem裝
{
if(str[j]>ch[i])
st=(ch1[i]-'0'+'9'-str[j])+step;
else
st=(str[j]-'0'+'9'-ch1[i])+step;
}
else
{
if(str[j]>ch1[i])
st=(str[j]-ch1[i])+step;
else
st=(ch1[i]-str[j])+step;
}
for(e=0;e<j;e++)//把ch1的第j個(gè)以前的數(shù)和str第j個(gè)數(shù)以前相同的數(shù)先裝起來(lái)
tem[e]=ch1[e];
tem[j]=str[j];//當(dāng)前第j個(gè)位置改變成str和第j個(gè)
if(i!=j)//不相等說(shuō)明是回朔了，i比j大
{
for(e=j+1;e<=i;e++)//把第i個(gè)要放到第j個(gè)前面，那么ch1中從第j個(gè)開(kāi)始位置開(kāi)始到第i個(gè)位置都往后存放一位，
tem[e]=ch1[e-1];
for(;e<4;e++) //把第i個(gè)位置以后的數(shù)裝入
tem[e]=ch1[e];
}
else//相等說(shuō)明還沒(méi)有回朔，那么就直接存放
for(e=j+1;e<4;e++)
tem[e]=ch1[e];
//printf("%d %d %d %s %s\n",j,i,st+i-j,tem,ch1);
DFS(j+1,j,st+i-j,tem);//i-j的意思是把ch1里的第i個(gè)移到第j個(gè)位置，那么tem中從0－>i（包括第i個(gè)）都是與str相同
}
vist[x]=0;
}
int main()
{
int i,t,j,e,st;
char ch1[5];
scanf("%d",&t);
while(t--)
{
getchar();
scanf("%s",str);
getchar();
scanf("%s",ch);
flog=13322;
for(i=0;i<4;i++)//以ch中的第i個(gè)數(shù)為開(kāi)頭,并把頭一個(gè)變成str[0]相同
{
ch1[0]=ch[i];
for(j=0,e=1;j<4;j++)
if(j!=i)
ch1[e++]=ch[j];
if(str[0]-ch1[0]>=5||str[0]-ch1[0]<=-5)
{
if(str[0]>ch1[0])
st=(ch1[0]-'0'+'9'-str[0]);
else
st=(str[0]-'0'+'9'-ch1[0]);
}
else
{
if(str[0]>ch1[0])
st=(str[0]-ch1[0]);
else
st=(ch1[0]-str[0]);
}
ch1[0]=str[0];
//printf("%s\n",ch1);
//printf("%d\n",st+i);
DFS(1,0,st+i,ch1);//i是從第i個(gè)到第一個(gè)須要多少步，st是把ch[i]變成str[0]須要多少步
//printf("\n");
}
printf("%d\n",flog);
}
}
?
更多文章、技術(shù)交流、商務(wù)合作、聯(lián)系博主
微信掃碼或搜索：z360901061
微信掃一掃加我為好友
QQ號(hào)聯(lián)系： 360901061
您的支持是博主寫(xiě)作最大的動(dòng)力，如果您喜歡我的文章，感覺(jué)我的文章對(duì)您有幫助，請(qǐng)用微信掃描下面二維碼支持博主2元、5元、10元、20元等您想捐的金額吧，狠狠點(diǎn)擊下面給點(diǎn)支持吧，站長(zhǎng)非常感激您！手機(jī)微信長(zhǎng)按不能支付解決辦法：請(qǐng)將微信支付二維碼保存到相冊(cè)，切換到微信，然后點(diǎn)擊微信右上角掃一掃功能，選擇支付二維碼完成支付。
【本文對(duì)您有幫助就好】元
