- #Your code here
- #You can import some modules or create additional functions
- #reset the dict and store the new info
- import copy
- def reset(d):
- for key in d.keys():
- d[key] = None
- return d
- def 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-testing
- if __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://www.codesnippet.cn/detail/041120136900.html
来源: http://www.codesnippet.cn/detail/041120136900.html