Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- class Node:
- def __init__(self, x, y, balance, matrix):
- self.x = x
- self.y = y
- self.balance = balance
- self.matrix = matrix
- def __hash__(self):
- return self.x ^ self.y
- def __eq__(self, other):
- return self.x == other.x and self.y == other.y
- def neighbour_list(self):
- neighbour_list = []
- x = self.x
- y = self.y
- balance = self.balance
- matrix = self.matrix
- if x > 0:
- if matrix[y][x - 1]:
- if balance:
- neighbour_list.append(Node(x - 1, y, balance - 1, matrix))
- else:
- neighbour_list.append(Node(x - 1, y, balance, matrix))
- if x < len(matrix[0]) - 1:
- if matrix[y][x + 1]:
- if balance:
- neighbour_list.append(Node(x + 1, y, balance - 1, matrix))
- else:
- neighbour_list.append(Node(x + 1, y, balance, matrix))
- if y > 0:
- if matrix[y - 1][x]:
- if balance:
- neighbour_list.append(Node(x, y - 1, balance - 1, matrix))
- else:
- neighbour_list.append(Node(x, y - 1, balance, matrix))
- if y < len(matrix) - 1:
- if matrix[y + 1][x]:
- if balance:
- neighbour_list.append(Node(x, y + 1, balance - 1, matrix))
- else:
- neighbour_list.append(Node(x, y + 1, balance, matrix))
- return neighbour_list
- def answer(maze):
- from collections import deque
- def f(root_x, root_y, goal_x, goal_y, maze):
- root = Node(root_x , root_y, 1, maze)
- distance_dict = {root: 1}
- queue = deque([root])
- while queue:
- current_node = queue.popleft()
- for child in current_node.neighbour_list():
- if child not in distance_dict.keys():
- distance_dict[child] = distance_dict[current_node] + 1
- if child.x == goal_x and child.y == goal_y:
- return distance_dict[child]
- else:
- queue.append(child)
- return "Path not found"
- top_to_bottom = f(0,0, len(maze[0])-1, len(maze)-1, maze)
- bottom_to_top = f(len(maze[0])-1, len(maze)-1, 0, 0, maze)
- if top_to_bottom == "Path not found":
- return bottom_to_top
- else:
- return top_to_bottom
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement