這個題我看了，都是推薦的神馬雙向廣搜，難道這個深搜你們都木有發現？還是特意留個機會給我裝逼？
Open the Lock
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others)
Total Submission(s): 3014 Accepted Submission(s): 1323
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.
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.
Output
For each test case, print the minimal steps in one line.
Sample Input
2
1234
2144
1111
9999
Sample Output
2
4
#include <iostream>
#include <cstring>
#include <cmath>
using namespace std;
int visit[4]={0},ss,a[4],b[4]; //visit記錄a[i]是否被訪問，ss用來記錄暴力過程中的最小值
int cmp(int s) //這個是用來記錄從當前這樣的狀態不左右移動最少要多少次
{
int i,sum,aa[4]={s/1000,s/100%10,s/10%10,s%10}; //因為進來的是一個數字，所以用數組把它閹了，嘿嘿
for(i=sum=0;i<4;i++) //一位一位的開鎖
{
if(abs(aa[i]-b[i])<5)sum+=abs(aa[i]-b[i]);
else sum+=9-abs(aa[i]-b[i]);
}return sum;
}
void dfs(int sum,int s) //dfs裡面進來的sum是當前的這個合成的數字，也就是不停移動得到的數組，s是記錄移動次數
{
int i;
if(sum>999) //當sum>999也就是說sum是一個四位數時說明新的那個開鎖初始狀態OK了
{
i=cmp(sum)+s; //這時把sum和數組b開鎖的次數和用s記錄的移動的次數記錄下來
if(i<ss)ss=i; //比較，ss記錄最小開鎖操作
return;
}
for(i=0;i<4;i++)
{
if(!visit[i])
{
visit[i]=1;
dfs(sum*10+a[i],s++); //要是你聰明，會看到這裡的一個重要的步驟，就是s++，別小看了，這說明下一次再在for循環裡面取數就是在這次的數移動一位得到的，本體就是這個才是重點呢
visit[i]=0;
}
}
}
int main (void)
{
int i,j,k,l,n,m,t;
cin>>t;
while(t--&&cin>>n>>m)
{
for(i=3,j=1;i>=0;i--,j*=10)
{
a[i]=n/j%10;
b[i]=m/j%10;
}
ss=99999;
dfs(0,0);
cout<<ss<<endl;
}
return 0;
}
