迷宫成程序，迷宫程序,原本是checkio上的

迷宫成程序，迷宫程序,原本是checkio上的

原本是checkio上的一个一道迷宫题目，写了大家分享一下。注释我是自己写的英文，有可能看不懂，呵呵。算法的思路比较简单，就是查找位置，判断方向，回溯前进等。不过需要注意前进的时候切勿成环哦。

#Your code here#You can import some modules or create additional functions#reset the dict and store the new infoimport copydef reset(d):    for key in d.keys():        d[key] = None    return ddef checkio(data):    #Your code here    #It's main function. Don't remove this function    #It's using for auto-testing and must return a result for check.    #replace this for solution    #This is just example for first maze    #pre-direction sotres the pre-cell    path = []    cell = {'direction':None,'pre_direct':None,'px':1,'py':1,'s':None,'n':None,'e':None,'w':None,}    cell_count=0    px = 1    py = 1    find_route = False    check_flag = False    #store the pre_cell info    #put he first cell into path    if data[px+1][py] == 0 and cell['s'] == None:      cell['s'] = 1      cell['direction'] = 's'      px = px + 1    elif data[px][py+1] == 0 and cell['e'] == None:      cell['e'] = 1      cell['direction'] = 'e'      py =  py + 1    elif data[px-1][py] == 0 and cell['n'] == None:      cell['n'] = 1      cell['direction'] = 'n'      px = px - 1    elif data[px][py-1] == 0 and cell['w'] == None:      cell['w'] = 1      cell['direction'] ='w'      py = py - 1    path.append(copy.deepcopy(cell))    pre_cell = path[0]    cell = reset(cell)    while True:      if px == 10 and py == 10:        find_route = True        break      elif not path:        break      #init a new cell basic info       cell['pre_direct'] = pre_cell      cell['px']  =  px      cell['py'] =   py      circle_flag = False      #visit the south.if the south is clear and put the point info into the cell and refresh the info of the dict.      #if can not find the right pop it       #need to judge the pre-cell direction      #can not become a circle      for temp_elem in path:        if temp_elem['px']==px and temp_elem['py'] == py:            circle_flag = True      if circle_flag == False:          if data[px+1][py] == 0 and cell['s'] == None and pre_cell['direction'] != 'n':            cell['s'] = 1            cell['direction'] = 's'            px = px + 1            check_flag = True          elif data[px][py+1] == 0 and cell['e'] == None and pre_cell['direction'] != 'w':            cell['e'] = 1            cell['direction'] = 'e'            py = py + 1            check_flag = True          elif data[px-1][py] == 0 and cell['n'] == None and pre_cell['direction'] != 's':            cell['n'] = 1            cell['direction'] = 'n'            px = px - 1            check_flag = True          elif data[px][py-1] == 0 and cell['w'] == None and pre_cell['direction'] != 'e':            cell['w'] = 1            cell['direction'] = 'w'            py = py - 1            check_flag = True      if check_flag == True:        path.append(copy.deepcopy(cell))        pre_cell = path[-1]        cell = reset(cell)        check_flag = False      elif path:        cell = path.pop()        px = cell['px']        py = cell['py']        pre_cell = cell['pre_direct']      #when the pushing  condation can be  not satisfied,pop the cell out of the stack    re = ''    if find_route == True:        for elem in path:            re = re + elem['direction'].upper()    else:        re = 'can not find'    return re#Some hints#Look to graph search algorithms#Don't confuse these with tree search algorithms#This code using only for self-checking and not necessary for auto-testingif __name__ == '__main__':    print(checkio(    [[1,1,1,1,1,1,1,1,1,1,1,1],    [1,0,0,0,0,0,0,0,0,0,0,1],    [1,1,1,0,1,1,1,1,0,1,1,1],    [1,0,0,0,0,0,0,0,0,0,0,1],    [1,0,1,1,1,0,1,1,1,1,1,1],    [1,0,0,1,0,0,0,0,0,0,0,1],    [1,1,0,1,1,1,1,1,1,0,1,1],    [1,0,0,0,0,0,1,0,0,0,0,1],    [1,1,1,1,1,0,1,0,0,1,0,1],    [1,0,0,0,0,0,1,1,1,1,1,1],    [1,0,1,1,1,0,0,0,0,0,0,1],    [1,1,1,1,1,1,1,1,1,1,1,1]]))    #be carefull with infinity loop    print(checkio([           [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1],           [1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1],           [1, 0, 1, 1, 1, 1, 1, 1, 0, 1, 1, 1],           [1, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 1],           [1, 0, 1, 0, 1, 1, 1, 1, 1, 1, 0, 1],           [1, 0, 1, 0, 1, 0, 0, 0, 0, 0, 0, 1],           [1, 0, 0, 0, 1, 1, 0, 1, 1, 1, 0, 1],           [1, 0, 1, 0, 0, 0, 0, 1, 0, 1, 1, 1],           [1, 0, 1, 1, 0, 1, 0, 0, 0, 0, 0, 1],           [1, 0, 1, 0, 0, 1, 1, 1, 1, 1, 0, 1],           [1, 0, 0, 0, 1, 1, 0, 0, 0, 0, 0, 1],           [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1]]))       #be carefull with infinity loop    print(checkio([           [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1],           [1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1],           [1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1],           [1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1],           [1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1],           [1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1],           [1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1],           [1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1],           [1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1],           [1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1],           [1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1],           [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1]       ]))    print(checkio([           [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1],           [1, 0, 0, 0, 1, 0, 0, 0, 1, 0, 0, 1],           [1, 0, 1, 0, 0, 0, 1, 0, 0, 0, 1, 1],           [1, 0, 0, 0, 1, 0, 0, 0, 1, 0, 0, 1],           [1, 0, 1, 0, 0, 0, 1, 0, 0, 0, 1, 1],           [1, 0, 0, 0, 1, 0, 0, 0, 1, 0, 0, 1],           [1, 0, 1, 0, 0, 0, 1, 0, 0, 0, 1, 1],           [1, 0, 0, 0, 1, 0, 0, 0, 1, 0, 0, 1],           [1, 0, 1, 0, 0, 0, 1, 0, 0, 0, 1, 1],           [1, 0, 0, 0, 1, 0, 0, 0, 1, 0, 0, 1],           [1, 0, 1, 0, 0, 0, 1, 0, 0, 0, 0, 1],           [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1],           ]))#该片段来自于http://byrx.net