




from __future__ import annotations

__lowerCAmelCase	:       Optional[Any]     =	list[tuple[int, int]]

__lowerCAmelCase	:       Optional[int]     =	[
    [0, 0, 0, 0, 0, 0, 0],
    [0, 1, 0, 0, 0, 0, 0],  # 0 are free path whereas 1's are obstacles
    [0, 0, 0, 0, 0, 0, 0],
    [0, 0, 1, 0, 0, 0, 0],
    [1, 0, 1, 0, 0, 0, 0],
    [0, 0, 0, 0, 0, 0, 0],
    [0, 0, 0, 0, 1, 0, 0],
]

__lowerCAmelCase	:       str     =	([-1, 0], [0, -1], [1, 0], [0, 1])  # up, left, down, right




class 					snake_case__							:
				"""simple docstring"""



				def __init__(   self       :  Optional[Any]      ,   __lowerCamelCase       :  int      ,   __lowerCamelCase       :  int      ,   __lowerCamelCase       :  int      ,   __lowerCamelCase       :  int      ,   __lowerCamelCase       :  float      ,   __lowerCamelCase       :  Node | None      ,   )      ->  Any:
							a					=    pos_x
							a					=    pos_y
							a					=    (pos_y, pos_x)
							a					=    goal_x
							a					=    goal_y
							a					=    g_cost
							a					=    parent
							a					=    self.calculate_heuristic()





				def 							__UpperCAmelCase							(   self       :  Tuple							)      ->  float:
							a					=    abs(self.pos_x - self.goal_x							)
							a					=    abs(self.pos_y - self.goal_y							)
							return dx + dy





				def __lt__(   self       :  str      ,   __lowerCamelCase       :  Tuple							)      ->  bool:
							return self.f_cost < other.f_cost




class 					snake_case__							:
				"""simple docstring"""



				def __init__(   self       :  Dict      ,   __lowerCamelCase       :  tuple[int, int]      ,   __lowerCamelCase       :  tuple[int, int]							)      ->  List[str]:
							a					=    Node(start[1]      ,   start[0]      ,   goal[1]      ,   goal[0]      ,   0      ,   __lowerCamelCase							)
							a					=    Node(goal[1]      ,   goal[0]      ,   goal[1]      ,   goal[0]      ,   9_99_99      ,   __lowerCamelCase							)

							a					=    [self.start]
							a					=    []

							a					=    False





				def 							__UpperCAmelCase							(   self       :  str							)      ->  Path | None:
							while self.open_nodes:
										# Open Nodes are sorted using __lt__
										self.open_nodes.sort()
										a					=    self.open_nodes.pop(0							)

										if current_node.pos == self.target.pos:
													a					=    True
													return self.retrace_path(__lowerCamelCase							)

										self.closed_nodes.append(__lowerCamelCase							)
										a					=    self.get_successors(__lowerCamelCase							)

										for child_node in successors:
													if child_node in self.closed_nodes:
																continue

													if child_node not in self.open_nodes:
																self.open_nodes.append(__lowerCamelCase							)
													else:
																# retrieve the best current path
																a					=    self.open_nodes.pop(self.open_nodes.index(__lowerCamelCase							)							)

																if child_node.g_cost < better_node.g_cost:
																			self.open_nodes.append(__lowerCamelCase							)
																else:
																			self.open_nodes.append(__lowerCamelCase							)

							if not self.reached:
										return [self.start.pos]
							return None





				def 							__UpperCAmelCase							(   self       :  List[str]      ,   __lowerCamelCase       :  Node							)      ->  list[Node]:
							a					=    []
							for action in delta:
										a					=    parent.pos_x + action[1]
										a					=    parent.pos_y + action[0]

										if not (0 <= pos_x <= len(grid[0]							) - 1 and 0 <= pos_y <= len(__lowerCamelCase							) - 1):
													continue

										if grid[pos_y][pos_x] != 0:
													continue

										successors.append(
										    Node(
										        __lowerCamelCase      ,   __lowerCamelCase      ,   self.target.pos_y      ,   self.target.pos_x      ,   parent.g_cost + 1      ,   __lowerCamelCase      ,   )							)
							return successors





				def 							__UpperCAmelCase							(   self       :  List[Any]      ,   __lowerCamelCase       :  Node | None							)      ->  Path:
							a					=    node
							a					=    []
							while current_node is not None:
										path.append((current_node.pos_y, current_node.pos_x)							)
										a					=    current_node.parent
							path.reverse()
							return path


if __name__ == "__main__":
		__lowerCAmelCase	:       List[str]     =	(0, 0)
		__lowerCAmelCase	:       str     =	(len(grid) - 1, len(grid[0]) - 1)
		for elem in grid:
				print(elem)

		print('------')

		__lowerCAmelCase	:       Any     =	GreedyBestFirst(init, goal)
		__lowerCAmelCase	:       Dict     =	greedy_bf.search()
		if path:
				for pos_x, pos_y in path:
						__lowerCAmelCase	:       Union[str, Any]     =	2

				for elem in grid:
						print(elem)












def     __magic_name__       (				A	:      int,						A	:      int,						A	:      int     ):






			'''simple docstring'''







			if exponent == 1:
						return base
			if exponent % 2 == 0:
						a					=    _modexpt(A,						exponent // 2,						A     ) % modulo_value
						return (x * x) % modulo_value
			else:
						return (base * _modexpt(A,						exponent - 1,						A     )) % modulo_value




def     __magic_name__       (				A	:      int = 1777,						A	:      int = 1855,						A	:      int = 8     ):






			'''simple docstring'''







			a					=    base
			for _ in range(1,						A     ):
						a					=    _modexpt(A,						A,						10**digits     )

			return result


if __name__ == "__main__":
		print(F'''{solution() = }''')






