算法学习之路|聪明的打字员
Description
阿兰是某机密部门的打字员，她现在接到一个任务：需要在一天之内输入几百个长度固定为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号位置上。当巧妙地使用上述六个特殊键之后，可以得到目标密码，这时光标允许停在任何一个位置。
现在，阿兰需要你的帮助，编写一个程序，求出录入一个密码需要的最少的击键次数。
Input
仅一行，含有两个长度为6的数，前者为初始密码，后者为目标密码，两个密码之间用一个空格隔开。
Output
仅一行，含有一个正整数，为最少需要的击键次数。
Sample Input
123456 654321
Sample Output
11
Source
Noi 01
题目分析：在状态的最后一位补一个记录光标然后BFS，两个剪枝
1.Up，Down只有在当前位和目标位不同时才进行，这是显然的
2.Left，Right时只有中间四位和目标位相同时才进行，因为移动光标不会影响数字的状态，因此数字位不同时，只移动光标没有什么意义
字符串用map哈希，g++跑了两个1000ms，然而c++ 300+过
# -*- coding: utf-8 -*-
import copy
queue=[]#0是队列的front
found=[]#确保搜索一次，即变来变去不会变回原来的样子
class node:
def __init__(self,string,count):
self.s=string #s[0]为当前光标位置
self.c=count
def bfs(endstr):
while len(queue)!=0:
cur=queue[0]#current
del queue[0]
if cur.s[1:]==endstr:
return cur.c
#Swap6
c=copy.deepcopy(cur)#防止原node变化
print c.s
print c.s[0]
if c.s[0]!=6 and c.s[c.s[0]]!=endstr[c.s[0]-1]:#剪枝
c.s[c.s[0]],c.s[6]=c.s[6],c.s[c.s[0]]
c.c+=1
if c.s not in found:
found.append(c.s)
queue.append(c)
#Swap1
c = copy.deepcopy(cur)
if c.s[0] != 1 and c.s[c.s[0]]!=endstr[c.s[0]-1]:
c.s[c.s[0]],c.s[1]=c.s[1],c.s[c.s[0]]
c.c+=1
if c.s not in found:
found.append(c.s)
queue.append(c)
#up
c = copy.deepcopy(cur)
if c.s[c.s[0]]!=endstr[c.s[0]-1] and c.s[c.s[0]]!=9:#当前位和目标位不同时才进行
#解释：
#destion:1 2 4---4 2 4 p=2,即使[0]，[2]互换，也多了一步，毫不起作用
#destion:1 2 4---3 2 4 p=2,[0][2]互换，多了5步
c.s[c.s[0]]+=1
c.c+=1
if c.s not in found:
found.append(c.s)
queue.append(c)
# down
c = copy.deepcopy(cur)
if c.s[c.s[0]] != endstr[c.s[0]-1] and c.s[c.s[0]]!=0:#剪枝
c = copy.deepcopy(cur)
c.s[c.s[0]]-=1
c.c+=1
if c.s not in found:
found.append(c.s)
queue.append(c)
#left
c = copy.deepcopy(cur)
if c.s[c.s[0]] == endstr[c.s[0]-1] and c.s[0]!=1:#剪枝
#只有当前位和目标位相同时才进行，因为移动光标不会影响数字的状态，
# 因此数字位不同时，只移动光标没有什么意义
c.s[0]-=1
c.c+=1
if c.s not in found:
found.append(c.s)
queue.append(c)
#right
c = copy.deepcopy(cur)
if c.s[c.s[0]] == endstr[c.s[0]-1] and c.s[0]!=6:#剪枝
c.s[0]+=1
c.c+=1
if c.s not in found:
found.append(c.s)
queue.append(c)
queue.append(node([1,1,2,3,4,5,6],0))
print bfs([6,5,4,3,2,1])