dfs/bfs--bfs

bfs

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 <stdio.h>
#include <string.h>
#include <queue>
using namespace std;

int vis[11][11][11][11];  
//将四位数的每一位共同组成一个地址，其中值表示是否已经访问过该值
 
struct node{
    int num[4],step;
}first,second; //两个node变量来存储输入的两个数 

void bfs(){
    node now,next;
    queue<node> q;
    //将控制台输入的第一个数据赋值给now并将其次数设置为0，压入队列 
    now = first;
    now.step = 0;
    q.push(now);
    
    //将该点对应的四位数按照地址储存到vis数组中，将该地址的值设置为1 
    vis[ now.num[0] ][ now.num[1] ][ now.num[2] ][ now.num[3] ] = 1;
    
	while(!q.empty()){
        now = q.front(); q.pop(); //将队列中的首个元素给now并将其弹出 
        if(now.num[0] == second.num[0] && now.num[1] == second.num[1] && now.num[2] == second.num[2] && now.num[3] == second.num[3]){
        //如果now的所有值等于second的所有值，代表已经完成了，打印结果并返回、。、 
            printf("%d\n",now.step);
            return ;
        }
        
        //三种操作 
        for(int i = 0; i<4; i++){ //+1
            next = now;
            next.num[i]++;
            if(next.num[i]==10)//9+1-->1 
                next.num[i] = 1;
                
            if(!vis[next.num[0]][next.num[1]][next.num[2]][next.num[3]]){
            //以该点四位数为地址的数是否已经访问 
                vis[next.num[0]][next.num[1]][next.num[2]][next.num[3]] = 1;
                next.step++;
                q.push(next);
            }
        }
        for(int i = 0; i<4; i++){ //-1
            next = now;
            next.num[i]--;
            if(next.num[i]==0) //1-1 --> 9
                next.num[i] = 9;
            if(!vis[next.num[0]][next.num[1]][next.num[2]][next.num[3]]){
                vis[next.num[0]][next.num[1]][next.num[2]][next.num[3]] = 1;
                next.step++;
                q.push(next);
            }
        }
        for(int i = 0; i<3; i++){ //交换
        	//邻位相交换 
            next = now;	//next = now = 1234  i=0;
            next.num[i] = now.num[i+1]; //next = 2234
            next.num[i+1] = now.num[i]; //next = 2134
        
		    if(!vis[next.num[0]][next.num[1]][next.num[2]][next.num[3]]){
                vis[next.num[0]][next.num[1]][next.num[2]][next.num[3]] = 1;
                next.step++;
                q.push(next);
            }
        }
    }
}
/*
*	演示：input:t=1 s1=1111 s2=9999
*			first -->1,1,1,1  second -->9,9,9,9
*			now = first   
*				/           |
*			2111 		    
*	vis[2][1][1][1]=1
*
*	思路：用vis四维数组来搞bfs，无脑的往三个方向上用bfs，即+1，-1，交换，
*		只要是还未被访问过的就压入队列，然后在继续。核心是每一个数都只能
*		被访问一次，那么就意味着第一个访问该数的就是最短的路径，即次数最
*		少 
*
*
*/
 
int main(){
    int t; //有多少组测试数据 
    char s1[5],s2[5]; //两个数 
    scanf("%d",&t);
    while(t--){
        scanf("%s%s",s1,s2);
        for(int i = 0; i<4; i++){
            first.num[i] = s1[i]-'0';  // first <-- s1
            second.num[i] = s2[i]-'0'; // second <-- s2
        }
        memset(vis,0,sizeof(vis)); //初始化 
        bfs();
    }
    return 0;
}