#4267. 「2022.03五级」数字变换 暂未评定

时间限制:1000 ms 内存限制:128 MiB 标准输入输出
题目类型:传统 评测方式:文本比较
上传者: root

题目描述

给定一个包含 5 个数字(0-9)的字符串, 例如 “02943”, 请将“12345”变换到它。 你可以采取 3 种操作进行变换

1、 交换相邻的两个数字

2、 将一个数字加 1。 如果加 1 后大于 9, 则变为 0

3、 将一个数字加倍。 如果加倍后大于 9,则将其变为加倍后的结果除以 10 的余数。

最多只能用第 2 种操作 3 次, 第 3 种操作 2 次 求最少经过多少次操作可以完成变换。

输入格式

有最多 100,000 组数据 每组数据就是包含 5 个数字的字符串

输出格式

对每组数据, 输出将"12345"变换到给定字符串所需要的最少操作步数。 如果无法变换成功, 输出-1

样例

样例输入

12435
99999
12374

样例输出

1
-1
3

数据范围与提示

由于测试数据太多, 如果对每组数据都从头进行搜索, 就会超时。 建议先做预处理, 即以“12345” 作为初始状态做一遍彻底的广搜, 找出“12345” 经合法变换能够到达的所有字符串, 并记录到达这些字符串各需要多少步操作。 然后对读入的每组数据, 在上述预处理记录的结果中进行查询即可。