find shorttest path

た 入场券 2022-03-15 19:04 188阅读 0赞
  1. def find_shortest_path(maze):
  2. '''
  3. maze = [['X', 'X', 'O', 'S', 'X'],
  4. ['X', 'X', 'O', 'O', 'X'],
  5. ['X', 'X', 'O', 'X', 'X'],
  6. ['X', 'X', 'O', 'E', 'X']]'''
  7. a=[]
  8. b=[]
  9. s1=s2=e1=e2=0
  10. for i in range(len(maze)):
  11. for j in range(len(maze[0])):
  12. if maze[i][j]=='S':
  13. s1=i
  14. s2=j
  15. if maze[i][j]=='E':
  16. e1=i
  17. e2=j
  18. a.append([(s1,s2),])
  19. while len(a)>0:
  20. b=[]
  21. for aaa in a:
  22. #up
  23. aa=aaa[:]
  24. if aa[-1][0]-1>=0:
  25. if aa[-1][0]-1 == e1 and aa[-1][1] == e2:
  26. return len(aa)
  27. if maze[aa[-1][0]-1][aa[-1][1]]=='O' and (aa[-1][0]-1,aa[-1][1]) not in aa:
  28. aa.append((aa[-1][0] - 1, aa[-1][1]))
  29. b.append(aa)
  30. #left
  31. aa=aaa[:]
  32. if aa[-1][1]-1>=0:
  33. if aa[-1][0]==e1 and aa[-1][1]-1==e2:
  34. return len(aa)
  35. if maze[aa[-1][0]][aa[-1][1]-1]=='O' and (aa[-1][0],aa[-1][1]-1) not in aa:
  36. aa.append((aa[-1][0], aa[-1][1] - 1))
  37. b.append(aa)
  38. #right
  39. aa=aaa[:]
  40. if aa[-1][1]+1<len(maze[0]):
  41. if aa[-1][0] == e1 and aa[-1][1] +1 == e2:
  42. return len(aa)
  43. if maze[aa[-1][0]][aa[-1][1]+1]=='O' and (aa[-1][0],aa[-1][1]+1) not in aa:
  44. aa.append((aa[-1][0], aa[-1][1] + 1))
  45. b.append(aa)
  46. #down
  47. aa=aaa[:]
  48. if aa[-1][0]+1<len(maze):
  49. if aa[-1][0]+1==e1 and aa[-1][1]==e2:
  50. return len(aa)
  51. if maze[aa[-1][0]+1][aa[-1][1]]=='O' and (aa[-1][0]+1,aa[-1][1]) not in aa:
  52. aa.append((aa[-1][0] + 1, aa[-1][1]))
  53. b.append(aa)
  54. a=b
  55. return -1
  56. maze = [['X', 'O', 'O', 'O', 'X'],
  57. ['X', 'O', 'O', 'O', 'X'],
  58. ['X', 'O', 'O', 'O', 'O'],
  59. ['X', 'O', 'S', 'O', 'E']]
  60. print find_shortest_path(maze)

发表评论

表情:
评论列表 (有 0 条评论,188人围观)

还没有评论,来说两句吧...

相关阅读