题目

 J-Luggage Lock_第 46 届 ICPC 国际大学生程序设计竞赛亚洲区域赛（沈阳） (nowcoder.com)

题解

首先我们忽略起始数字，因为我们实际上可以把所有的起始数字转化为0000和密码转动起始数字 所以题目只有10000种输入（0000~9999）

考虑打表，开长度10000的表，由0000递推，每次转动一位，记录所需要转动到的最短的次数，总共有10种转动方法，求最短所以使用BFS

代码

（建议配合下面的编码流程食用）

#define _CRT_SECURE_NO_WARNINGS 1.
#include 
#include  
#include 
#include 
using namespace std;
const int N = 2e5 + 10;
int f[N];
//从右到左对应密码是的从左到右 （循环4次，每次*10，合成一个四位数）
int ne[10][4] = {
    {0,0,0,1},
    {0,0,1,0},
    {0,1,0,0},
    {1,0,0,0},
    {0,0,1,1},
    {0,1,1,0},
    {1,1,0,0},
    {0,1,1,1},
    {1,1,1,0},
    {1,1,1,1}
};
int main() {
    int t;
    scanf("%d", &t);
    memset(f, 0x3f3f3f3f, sizeof f);
    f[0] = 0;
    queue q;
    q.push(0);
    int fh[2] = { 1,-1 };//创建符号数组fh ， 处理逆序转动的情况
    while (!q.empty()){
        int hh = q.front();
        int tt = hh;
        q.pop();
        int num[4],nnum[4];
        //将要处理的四位数（tt），整理成 4 个独立的数储存在num数组
        for (int i = 0; i < 4; i++) {
            num[i]= tt%10;
            tt /= 10;
        }
        for (int g = 0; g < 2; g++) {
            for (int i = 0; i < 10; i++) {
                //sum: 将队列中的四个数整合成四位数
                //be：表示处于第几位数，每次循环 * 10
                int sum = 0, be = 1;
                for (int j = 0; j < 4; j++) {
                    // nnum[4]：储存转移后的每一位数
                    nnum[j] = (num[j] + fh[g] * ne[i][j] + 10) % 10;//（+10和%10用于处理逆序转动时，也就是fh = -1时）
                    sum += be * nnum[j];
                    be *= 10;
                    }
                if (f[sum] > f[hh] + 1) {
                    q.push(sum);
                    f[sum] = f[hh] + 1;
                }
            }
         }         
    }
    while (t--) {
        int a, b;
        scanf("%d%d", &a, &b);
        int sum = 0;
        for(int i = 0; i < 4; i++ ){
            sum *= 10;
            sum += (b % 10 - a % 10 + 10) % 10;
            a /= 10;
            b /= 10;
        }
        printf("%dn", f[sum]);
    }
    return 0;
}

编码流程编码流程：

编码流程：
一、打表
1、创建转移数组ne[]
（1）从右到左对应密码是的从左到右 （循环4次，每次*10，合成一个四位数）
（2）创建符号数组fh ， 处理逆序转动的情况
2、初始化f数组，f数组记录从0移动至f[i]所需的步数
3、建立队列
 （1） 将要处理的四位数（tt），整理成 4 个独立的数储存在num数组 
 （2） 进行三重循环 通过转移数组进行状态转移：
           sum: 将队列中的四个数整合成四位数
           be：表示处于第几位数，每次循环*10
            nnum[4]：储存转移后的每一个数
          （+10和%10用于处理逆序转动时，也就是fh = -1时）  
 （3）判断转移后的状态是非比原先的状态移动步数更少
         是的话，该状态入列，且用当前值f[hh]+1 替代原先值f[sum]。
二、输入始状态和末状态
  1、求出每一位的差值，差值为负数就+10%10使其变为正数
  2、将四个数的差值整合成四位数，然后查表得出答案。