题解

使用 bfs 的方式进行搜索，每次把目前得到的数拆出每一位，分别对这个数尝试加上某一位和减去某一位。注意记录每个数是否被访问过，以及注意每一次尝试加减某一位都要在原数上操作。

标程

#include <cstdio>
#include <iostream>
#include <cstring>
#include <queue>
using namespace std;
int d[1000005];
int digit[10];
int a, b, cnt;
queue<int> q;
void deal(int x) {
    cnt = 0;
    while (x) {
        digit[cnt++] = x % 10;
        x /= 10;
    }
}
int bfs() {
    memset(d, -1, sizeof(d));
    d[a] = 0;
    q.push(a);
    while (!q.empty()) {
        int now = q.front();
        q.pop();
        deal(now);
        for (int i = 0; i < cnt; i++) {
            if (now - digit[i] >= 1 && d[now - digit[i]] == -1) {
                d[now - digit[i]] = d[now] + 1;
                q.push(now - digit[i]);
            }
            if (now + digit[i] <= 1000000 && d[now + digit[i]] == -1) {
                d[now + digit[i]] = d[now] + 1;
                q.push(now + digit[i]);
            }
        }
    }
    return d[b];
}
int main() {
    cin >> a >> b;
    cout << bfs() << endl;
    return 0;
}