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位置方問過
for(i=x+1;i<4;i++)
if(vist[i]==0)
{
if(str[j]-ch1[i]>=5||str[j]-ch1[i]<=-5)//第一步，當(dāng)成立時，把ch1[i]加或減變成str[j]的所用時間加起來，會用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個以前的數(shù)和str第j個數(shù)以前相同的數(shù)先裝起來
tem[e]=ch1[e];
tem[j]=str[j];//當(dāng)前第j個位置改變成str和第j個
if(i!=j)//不相等說明是回朔了，i比j大
{
for(e=j+1;e<=i;e++)//把第i個要放到第j個前面，那么ch1中從第j個開始位置開始到第i個位置都往后存放一位，
tem[e]=ch1[e-1];
for(;e<4;e++) //把第i個位置以后的數(shù)裝入
tem[e]=ch1[e];
}
else//相等說明還沒有回朔，那么就直接存放
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個移到第j個位置，那么tem中從0－>i（包括第i個）都是與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個數(shù)為開頭,并把頭一個變成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個到第一個須要多少步，st是把ch[i]變成str[0]須要多少步
//printf("\n");
}
printf("%d\n",flog);
}
}
?
更多文章、技術(shù)交流、商務(wù)合作、聯(lián)系博主
微信掃碼或搜索：z360901061
微信掃一掃加我為好友
QQ號聯(lián)系： 360901061
您的支持是博主寫作最大的動力，如果您喜歡我的文章，感覺我的文章對您有幫助，請用微信掃描下面二維碼支持博主2元、5元、10元、20元等您想捐的金額吧，狠狠點擊下面給點支持吧，站長非常感激您！手機(jī)微信長按不能支付解決辦法：請將微信支付二維碼保存到相冊，切換到微信，然后點擊微信右上角掃一掃功能，選擇支付二維碼完成支付。
【本文對您有幫助就好】元
