【正经题解】密码锁

定义一个结构体 $Node$ 表示状态，其中包含当前状态的数字和到达该状态的步数。
使用队列进行广度优先搜索，初始状态为起始数字和步数为 $0$ 。
在每一步操作中，分别进行增加 $1$ 、减少 $1$ 、交换相邻数字这三种操作，并将新状态加入队列。
使用数组 $vis$ 标记已经访问过的状态，避免重复搜索。
当找到目标状态时，输出到达该状态的步数。

#include<bits/stdc++.h>
using namespace std;

struct Node {
    int num, step;  // 表示当前状态的数字和到达该状态的步数
};

int t, n, m, b[4];

void bfs() {
    int vis[10000] = {0};
    queue<Node> q;
    q.push({n, 0});
    vis[n] = 1;

    while (!q.empty()) {
        Node n1 = q.front();
        q.pop();

        if (n1.num == m) {
            cout << n1.step << endl;
            return;
        }

        for (int i = 0; i < 4; i++) {
            // 增加1操作
            b[0] = n1.num / 1000, b[1] = n1.num % 1000 / 100, b[2] = n1.num % 100 / 10, b[3] = n1.num % 10;
            b[i]++;
            if (b[i] == 10) b[i] = 1;
            int sum = b[0] * 1000 + b[1] * 100 + b[2] * 10 + b[3]; 
            if (vis[sum] == 0) {
                vis[sum] = 1;
                q.push({sum, n1.step + 1});
            } 
        }

        for (int i = 0; i < 4; i++) {
            // 减少1操作
            b[0] = n1.num / 1000, b[1] = n1.num % 1000 / 100, b[2] = n1.num % 100 / 10, b[3] = n1.num % 10;
            b[i]--;
            if (b[i] == 0) b[i] = 9;
            int sum = b[0] * 1000 + b[1] * 100 + b[2] * 10 + b[3];
            if (vis[sum] == 0) {
                vis[sum] = 1;
                q.push({sum, n1.step + 1});
            } 
        }

        for (int i = 0; i < 3; i++) {
            // 交换相邻数字操作
            b[0] = n1.num / 1000, b[1] = n1.num % 1000 / 100, b[2] = n1.num % 100 / 10, b[3] = n1.num % 10;
            swap(b[i], b[i + 1]);
            int sum = b[0] * 1000 + b[1] * 100 + b[2] * 10 + b[3]; 
            if (vis[sum] == 0) {
                vis[sum] = 1;
                q.push({sum, n1.step + 1});
            } 
        } 
    }
}

int main() {
    cin >> t;
    while (t--) {
        cin >> n >> m; 
        bfs();
    }   
    return 0;
}