T3-3 Required Length

题意理解

给定整数 $n$ 和 $x$，每次操作可以选择 $x$ 十进制表示中的某个非零数字 $y$，将 $x$ 替换为 $x \times y$。求使 $x$ 的十进制长度恰好变为 $n$ 的最少操作次数。

---

思路分析

BFS 求最短路

由于要求最少操作次数，这是一个典型的 BFS 问题。每个数值是一个状态，每次操作是一条边。

关键观察：

1. 乘以 $0$：结果变成 $0$，永远无法增长，无意义
2. 乘以 $1$：数值不变，无意义
3. 乘以 $2 \sim 9$：数值严格增大，长度不减

因此只需考虑乘以 $\geq 2$ 的数字。

无解情况：

如果 $x$ 只包含数字 $0$ 和 $1$，那么只能乘 $1$，数值永远不变，无法达到更大的长度。

算法流程：

1. 如果初始长度已达到 $n$，输出 $0$
2. 用队列进行 BFS，初始状态为 $x$
3. 每次取出当前数 $cur$，枚举其所有 $\geq 2$ 的数字 $d$，计算 $nxt = cur \times d$
4. 若 $nxt$ 长度达到 $n$，返回步数
5. 若 $nxt$ 长度 $< n$ 且未访问过，加入队列
6. 队列为空仍未达到，返回 $-1$

---

参考代码

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

int getLen(long long x) {  // 获取x的十进制长度
    int len = 0;
    while (x) {  // 逐位统计
        len++;
        x /= 10;
    }
    return len;
}

int main() {
    int n;
    long long x;
    cin >> n >> x;  // 读入目标长度和初始数
    
    if (getLen(x) == n) {  // 初始长度已达到目标
        cout << 0 << endl;
        return 0;
    }
    
    set<long long> vis;  // 记录访问过的状态
    queue<pair<long long, int>> q;  // 队列存储(当前数, 操作次数)
    
    q.push({x, 0});  // 初始状态入队
    vis.insert(x);   // 标记已访问
    
    while (!q.empty()) {  // BFS主循环
        long long cur = q.front().first;   // 当前数
        int step = q.front().second;       // 当前操作次数
        q.pop();
        
        set<int> digits;  // 提取cur的所有数字（去重）
        long long tmp = cur;
        while (tmp) {
            int d = tmp % 10;
            if (d >= 2) digits.insert(d);  // 只考虑>=2的数字
            tmp /= 10;
        }
        
        for (int d : digits) {  // 枚举可乘的数字
            long long nxt = cur * d;  // 计算新的数
            
            if (getLen(nxt) == n) {  // 达到目标长度
                cout << step + 1 << endl;
                return 0;
            }
            
            if (getLen(nxt) < n && vis.find(nxt) == vis.end()) {  // 长度未超且未访问
                vis.insert(nxt);  // 标记访问
                q.push({nxt, step + 1});  // 入队继续搜索
            }
        }
    }
    
    cout << -1 << endl;  // 无法达到目标
    return 0;
}