UVA13049 Combination Lock

我们急需专业高手—— 一双能瞬间打开密码锁的手。 我们已经知道锁的初始状态和目标状态， 但我们需要有人能用最少的步数转动转轮， 以尽快开锁。

多轮密码锁有多个转轮，每个转轮可以顺时针或逆时针转动，以选定一个 $0$ 到 $9$ 的数字。数字是循环的，所以顺时针越过 $9$ 之后，下一个数字就是 $0$ 。 同样，逆时针越过 $0$ 之后，下一个数字就是 $9$ 。 给定密码锁的转轮数量、初始状态和目标状态，你需要找出从初始状态到目标状态所需的最少步数。转轮上每改变一个数字，就算作一步。例如，对于一个 $4$ 位密码锁，如果初始状态是“ $1234$ ”，目标状态是“ $2546$ ”，则至少需要 $7$ 步（从 $1$ 到 $2$ 需 $1$ 步，从 $2$ 到 $5$ 需 $3$ 步，从 $3$ 到 $4$ 需 $1$ 步，从 $4$ 到 $6$ 需 $2$ 步）。

输入的第一行将包含一个整数 $T$ （ $1 \le T \le 200$ ），表示测试用例的数量。 接下来的 $T$ 行中，每行会给你 $n$ 、 $\textit{initial}$ 和 $\textit{target}$ 。 其中 $n$ （ $1 \le n \le 100$ ）是一个整数，表示密码锁的转轮数量。 数字字符串 $\textit{initial}$ 和 $\textit{target}$ 分别表示锁的初始状态和目标状态。 两个字符串的长度都恰好为 $n$ ，且只包含十进制数字。

对于输入的每一行，请按照 `Case X: Y` 的格式输出用例编号和答案。 其中 $X$ 表示用例编号（从 $1$ 开始），$Y$ 表示从初始状态到目标状态所需的最少步数。 具体格式请参考样例输入输出。

翻译由 DeepSeek V4 完成