




from __future__ import annotations

__A        =    list[tuple[int, int]]

__A        =    [
    [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],
]

__A        =    ([-1, 0], [0, -1], [1, 0], [0, 1])  # up, left, down, right







class     __lowerCAmelCase :

			"""simple docstring"""







			def __init__(      self			,						lowerCamelCase__			,						lowerCamelCase__			,						lowerCamelCase__			,						lowerCamelCase__			,						lowerCamelCase__			,						lowerCamelCase__			,						)    ->      int:



							'''simple docstring'''
							__lowerCamelCase		       =    pos_x
							__lowerCamelCase		       =    pos_y
							__lowerCamelCase		       =    (pos_y, pos_x)
							__lowerCamelCase		       =    goal_x
							__lowerCamelCase		       =    goal_y
							__lowerCamelCase		       =    g_cost
							__lowerCamelCase		       =    parent
							__lowerCamelCase		       =    self.calculate_heuristic()


			def       lowercase_    (      self							)    ->      float:



							'''simple docstring'''
							__lowerCamelCase		       =    abs(self.pos_x - self.goal_x							)
							__lowerCamelCase		       =    abs(self.pos_y - self.goal_y							)
							return dx + dy






			def __lt__(      self			,						lowerCamelCase__							)    ->      bool:



							'''simple docstring'''
							return self.f_cost < other.f_cost







class     __lowerCAmelCase :

			"""simple docstring"""







			def __init__(      self			,						lowerCamelCase__			,						lowerCamelCase__							)    ->      Optional[Any]:



							'''simple docstring'''
							__lowerCamelCase		       =    Node(start[1]			,						start[0]			,						goal[1]			,						goal[0]			,						0			,						__SCREAMING_SNAKE_CASE							)
							__lowerCamelCase		       =    Node(goal[1]			,						goal[0]			,						goal[1]			,						goal[0]			,						99_999			,						__SCREAMING_SNAKE_CASE							)

							__lowerCamelCase		       =    [self.start]
							__lowerCamelCase		       =    []

							__lowerCamelCase		       =    False


			def       lowercase_    (      self							)    ->      Path | None:



							'''simple docstring'''
							while self.open_nodes:
											# Open Nodes are sorted using __lt__
											self.open_nodes.sort()
											__lowerCamelCase		       =    self.open_nodes.pop(0							)

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

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

											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(__SCREAMING_SNAKE_CASE							)
															else:
																			# retrieve the best current path
																			__lowerCamelCase		       =    self.open_nodes.pop(self.open_nodes.index(__SCREAMING_SNAKE_CASE							)							)

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

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


			def       lowercase_    (      self			,						lowerCamelCase__							)    ->      list[Node]:



							'''simple docstring'''
							__lowerCamelCase		       =    []
							for action in delta:
											__lowerCamelCase		       =    parent.pos_x + action[1]
											__lowerCamelCase		       =    parent.pos_y + action[0]

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

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

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






			def       lowercase_    (      self			,						lowerCamelCase__							)    ->      Path:



							'''simple docstring'''
							__lowerCamelCase		       =    node
							__lowerCamelCase		       =    []
							while current_node is not None:
											path.append((current_node.pos_y, current_node.pos_x)							)
											__lowerCamelCase		       =    current_node.parent
							path.reverse()
							return path


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

					print("------")

					__A        =    GreedyBestFirst(init, goal)
					__A        =    greedy_bf.search()
					if path:
										for pos_x, pos_y in path:
															__A        =    2

										for elem in grid:
															print(elem)










"""simple docstring"""





from __future__ import annotations

from typing import Generic, TypeVar

_SCREAMING_SNAKE_CASE					:				Optional[Any]					    =						TypeVar('''T''')






class      a						(					Generic[T]		):






    def __init__(       self     :							List[str]       ,						__SCREAMING_SNAKE_CASE     :							T					)     ->		None:
      lowerCamelCase_         =						data
      lowerCamelCase_         =						self
      lowerCamelCase_         =						0






class      a						(					Generic[T]		):






    def __init__(       self     :							Any					)     ->		None:
      # map from node name to the node object
      lowerCamelCase_         =						{}






    def    UpperCamelCase       (       self     :							List[str]       ,						__SCREAMING_SNAKE_CASE     :							T					)     ->		None:
      # create a new set with x as its member
      lowerCamelCase_         =						DisjointSetTreeNode(__SCREAMING_SNAKE_CASE					)






    def    UpperCamelCase       (       self     :							Optional[int]       ,						__SCREAMING_SNAKE_CASE     :							T					)     ->		DisjointSetTreeNode[T]:
      # find the set x belongs to (with path-compression)
      lowerCamelCase_         =						self.map[data]
      if elem_ref != elem_ref.parent:
        lowerCamelCase_         =						self.find_set(elem_ref.parent.data					)
      return elem_ref.parent






    def    UpperCamelCase       (       self     :							str       ,						__SCREAMING_SNAKE_CASE     :							DisjointSetTreeNode[T]       ,						__SCREAMING_SNAKE_CASE     :							DisjointSetTreeNode[T]					)     ->		None:
      # helper function for union operation
      if nodea.rank > nodea.rank:
        lowerCamelCase_         =						nodea
      else:
        lowerCamelCase_         =						nodea
        if nodea.rank == nodea.rank:
          nodea.rank += 1






    def    UpperCamelCase       (       self     :							List[str]       ,						__SCREAMING_SNAKE_CASE     :							T       ,						__SCREAMING_SNAKE_CASE     :							T					)     ->		None:
      # merge 2 disjoint sets
      self.link(self.find_set(__SCREAMING_SNAKE_CASE					)       ,						self.find_set(__SCREAMING_SNAKE_CASE					)					)






class      a						(					Generic[T]		):






    def __init__(       self     :							Optional[int]					)     ->		None:
      # connections: map from the node to the neighbouring nodes (with weights)
      lowerCamelCase_         =						{}






    def    UpperCamelCase       (       self     :							Optional[int]       ,						__SCREAMING_SNAKE_CASE     :							T					)     ->		None:
      # add a node ONLY if its not present in the graph
      if node not in self.connections:
        lowerCamelCase_         =						{}






    def    UpperCamelCase       (       self     :							Tuple       ,						__SCREAMING_SNAKE_CASE     :							T       ,						__SCREAMING_SNAKE_CASE     :							T       ,						__SCREAMING_SNAKE_CASE     :							int					)     ->		None:
      # add an edge with the given weight
      self.add_node(__SCREAMING_SNAKE_CASE					)
      self.add_node(__SCREAMING_SNAKE_CASE					)
      lowerCamelCase_         =						weight
      lowerCamelCase_         =						weight






    def    UpperCamelCase       (       self     :							List[Any]					)     ->		GraphUndirectedWeighted[T]:
      lowerCamelCase_         =						[]
      lowerCamelCase_         =						set()
      for start in self.connections:
        for end in self.connections[start]:
          if (start, end) not in seen:
            seen.add((end, start)					)
            edges.append((start, end, self.connections[start][end])					)
      edges.sort(key=lambda __SCREAMING_SNAKE_CASE					: x[2]					)

      # creating the disjoint set
      lowerCamelCase_         =						DisjointSetTree[T]()
      for node in self.connections:
        disjoint_set.make_set(__SCREAMING_SNAKE_CASE					)

      # MST generation
      lowerCamelCase_         =						0
      lowerCamelCase_         =						0
      lowerCamelCase_         =						GraphUndirectedWeighted[T]()
      while num_edges < len(self.connections					) - 1:
        lowerCamelCase_     ,	lowerCamelCase_     ,	lowerCamelCase_         =						edges[index]
        index += 1
        lowerCamelCase_         =						disjoint_set.find_set(__SCREAMING_SNAKE_CASE					)
        lowerCamelCase_         =						disjoint_set.find_set(__SCREAMING_SNAKE_CASE					)
        if parent_u != parent_v:
          num_edges += 1
          graph.add_edge(__SCREAMING_SNAKE_CASE       ,						__SCREAMING_SNAKE_CASE       ,						__SCREAMING_SNAKE_CASE					)
          disjoint_set.union(__SCREAMING_SNAKE_CASE       ,						__SCREAMING_SNAKE_CASE					)
      return graph




