Advertisement
Guest User

harun plz give me luck

a guest
Mar 25th, 2017
105
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 2.47 KB | None | 0 0
  1. class Node:
  2.  
  3. def __init__(self, x, y, balance, matrix):
  4. self.x = x
  5. self.y = y
  6. self.balance = balance
  7. self.matrix = matrix
  8.  
  9. def __hash__(self):
  10. return self.x ^ self.y
  11.  
  12. def __eq__(self, other):
  13. return self.x == other.x and self.y == other.y
  14.  
  15. def neighbour_list(self):
  16. neighbour_list = []
  17. x = self.x
  18. y = self.y
  19. balance = self.balance
  20. matrix = self.matrix
  21.  
  22. if x > 0:
  23. if matrix[y][x - 1]:
  24. if balance:
  25. neighbour_list.append(Node(x - 1, y, balance - 1, matrix))
  26. else:
  27. neighbour_list.append(Node(x - 1, y, balance, matrix))
  28.  
  29. if x < len(matrix[0]) - 1:
  30. if matrix[y][x + 1]:
  31. if balance:
  32. neighbour_list.append(Node(x + 1, y, balance - 1, matrix))
  33. else:
  34. neighbour_list.append(Node(x + 1, y, balance, matrix))
  35.  
  36. if y > 0:
  37. if matrix[y - 1][x]:
  38. if balance:
  39. neighbour_list.append(Node(x, y - 1, balance - 1, matrix))
  40. else:
  41. neighbour_list.append(Node(x, y - 1, balance, matrix))
  42.  
  43. if y < len(matrix) - 1:
  44. if matrix[y + 1][x]:
  45. if balance:
  46. neighbour_list.append(Node(x, y + 1, balance - 1, matrix))
  47. else:
  48. neighbour_list.append(Node(x, y + 1, balance, matrix))
  49.  
  50. return neighbour_list
  51.  
  52. def answer(maze):
  53. from collections import deque
  54.  
  55. def f(root_x, root_y, goal_x, goal_y, maze):
  56. root = Node(root_x , root_y, 1, maze)
  57. distance_dict = {root: 1}
  58. queue = deque([root])
  59.  
  60. while queue:
  61. current_node = queue.popleft()
  62.  
  63. for child in current_node.neighbour_list():
  64.  
  65. if child not in distance_dict.keys():
  66. distance_dict[child] = distance_dict[current_node] + 1
  67. if child.x == goal_x and child.y == goal_y:
  68. return distance_dict[child]
  69. else:
  70. queue.append(child)
  71. return "Path not found"
  72.  
  73. top_to_bottom = f(0,0, len(maze[0])-1, len(maze)-1, maze)
  74. bottom_to_top = f(len(maze[0])-1, len(maze)-1, 0, 0, maze)
  75.  
  76. if top_to_bottom == "Path not found":
  77. return bottom_to_top
  78. else:
  79. return top_to_bottom
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement