NOI2001聪明的打字员

大榕树 \ 信息学奥赛 \ 竞赛题库

NOI2001聪明的打字员

原文链接：http://www.mydrs.org/program/list.asp?id=209
clever.pas/c/cpp
　　阿兰是某机密部门的打字员，她现在接到一个任务：需要在一天之内输入几百个长度固定为6的密码。当然，她希望输入的过程中敲击键盘的总次数越少越好。
　　不幸的是，出于保密的需要，该部门用于输入密码的键盘是特殊设计的，键盘上没有数字键，而只有以下六个键：Swap0, Swap1, Up, Down, Left, Right，为了说明这6个键的作用，我们先定义录入区的6个位置的编号，从左至右依次为1，2，3，4，5，6。下面列出每个键的作用：
　　Swap0：按Swap0，光标位置不变，将光标所在位置的数字与录入区的1号位置的数字（左起第一个数字）交换。如果光标已经处在录入区的1号位置，则按Swap0键之后，录入区的数字不变；
　　Swap1：按Swap1，光标位置不变，将光标所在位置的数字与录入区的6号位置的数字（左起第六个数字）交换。如果光标已经处在录入区的6号位置，则按Swap1键之后，录入区的数字不变；
　　Up：按Up，光标位置不变，将光标所在位置的数字加1（除非该数字是9）。例如，如果光标所在位置的数字为2，按Up之后，该处的数字变为3；如果该处数字为9，则按Up之后，数字不变，光标位置也不变；
　　Down：按Down，光标位置不变，将光标所在位置的数字减1（除非该数字是0），如果该处数字为0，则按Down之后，数字不变，光标位置也不变；
　　Left：按Left，光标左移一个位置，如果光标已经在录入区的1号位置（左起第一个位置）上，则光标不动；
　　Right：按Right，光标右移一个位置，如果光标已经在录入区的6号位置（左起第六个位置）上，则光标不动。
　　当然，为了使这样的键盘发挥作用，每次录入密码之前，录入区总会随机出现一个长度为6的初始密码，而且光标固定出现在1号位置上。当巧妙地使用上述六个特殊键之后，可以得到目标密码，这时光标允许停在任何一个位置。
　　现在，阿兰需要你的帮助，编写一个程序，求出录入一个密码需要的最少的击键次数。
输入文件（clever.in）
　　文件仅一行，含有两个长度为6的数，前者为初始密码，后者为目标密码，两个密码之间用一个空格隔开。
输出文件（clever.out）
　　文件仅一行，含有一个正整数，为最少需要的击键次数。
输入样例
123456 654321
输出样例
11
样例说明：
　　初始密码是123456，光标停在数字1上。对应上述最少击键次数的击键序列为：
击键序列：
击键后的录入区
（下划线表示光标所在位置）

　 123456

Swap1
623451

Right
623451

Swap0
263451

Down
253451

Right
253451

Up
254451

Right
254451

Down
254351

Right
254351

Up
254361

Swap0
654321

　　最少的击键次数为11。

作者：NOI2001
来源：NOI2001
时间：2001-09-03

上一篇：NOI2001食物链
下一篇：NOI2001反正切函数的应用