题目名称 299. [NOI 2001]聪明的打字员
输入输出 clever.in/out
难度等级
时间限制 3000 ms (3 s)
内存限制 128 MiB
测试数据 10
题目来源 GravatarBYVoid 于2009-03-17加入
开放分组 全部用户
提交状态
分类标签
NOI 搜索法 散列
分享题解
通过:37, 提交:140, 通过率:26.43%
Gravatar我想 100 0.006 s 10.63 MiB Pascal
GravatarQILIN 100 0.010 s 13.84 MiB C++
GravatarU.N.A 100 0.067 s 16.59 MiB C++
Gravatartest 100 0.106 s 23.20 MiB C++
GravatarHouJikan 100 0.121 s 6.99 MiB C++
GravatarZhouZn1 100 0.169 s 1.26 MiB Pascal
Gravatar旺仔小馒头 100 0.251 s 9.85 MiB C++
GravatarZhyz 100 0.568 s 18.23 MiB Pascal
Gravatar众神 隐人 100 1.601 s 6.99 MiB C++
GravatarEddy2008 100 2.451 s 100.45 MiB C++
关于 聪明的打字员 的近10条评论(全部评论)
好吧就是暴搜……可能当年内存没这么大吧
Gravatarcstdio
2014-07-05 23:07 2楼
七维数
Var
used:array[1..6,0..9,0..9,0..9,0..9,0..9,0..9]of boolean;
tar:array[1..6,0..9,0..9,0..9,0..9,0..9,0..9]of boolean;
GravatarTruth.Cirno
2012-10-30 07:52 1楼

299. [NOI 2001]聪明的打字员

★   输入文件:clever.in   输出文件:clever.out   简单对比
时间限制:3 s   内存限制:128 MiB

阿兰是某机密部门的打字员,她现在接到一个任务:需要在一天之内输入几百个长度固定为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号位置上。当巧妙地使用上述六个特殊键之后,可以得到目标密码,这时光标允许停在任何一个位置。 现在,阿兰需要你的帮助,编写一个程序,求出录入一个密码需要的最少的击键次数。

输入文件

文件仅一行,含有两个长度为6的数,前者为初始密码,后者为目标密码,两个密码之间用一个空格隔开。

输出文件

文件仅一行,含有一个正整数,为最少需要的击键次数。

输入样例

123456 654321

输出样例

11

样例说明:

初始密码是123456,光标停在数字1上。对应上述最少击键次数的击键序列为:

Image:Clever.gif

最少的击键次数为11。