
"""simple docstring"""


from __future__ import annotations

SCREAMING_SNAKE_CASE      =     [
    [-1, 0],  # left
    [0, -1],  # down
    [1, 0],  # right
    [0, 1],  # up
]



def 	lowerCamelCase__			(							UpperCAmelCase_		,      UpperCAmelCase_		,      UpperCAmelCase_		,      UpperCAmelCase_		,      UpperCAmelCase_		,      )->							tuple[list[list[int]], list[list[int]]]:







       """simple docstring"""
       UpperCamelCase					 =		[
           [0 for col in range(len(grid[0]				)				)] for row in range(len(UpperCAmelCase_				)				)
       ]  # the reference grid
       UpperCamelCase					 =		1
       UpperCamelCase					 =		[
           [0 for col in range(len(grid[0]				)				)] for row in range(len(UpperCAmelCase_				)				)
       ]  # the action grid

       UpperCamelCase					 =		init[0]
       UpperCamelCase					 =		init[1]
       UpperCamelCase					 =		0
       UpperCamelCase					 =		g + heuristic[x][y]  # cost from starting cell to destination cell
       UpperCamelCase					 =		[[f, g, x, y]]

       UpperCamelCase					 =		False  # flag that is set when search is complete
       UpperCamelCase					 =		False  # flag set if we can't find expand

       while not found and not resign:
              if len(UpperCAmelCase_				) == 0:
                     raise ValueError("Algorithm is unable to find solution"				)
              else:  # to choose the least costliest action so as to move closer to the goal
                     cell.sort()
                     cell.reverse()
                     UpperCamelCase					 =		cell.pop()
                     UpperCamelCase					 =		next_cell[2]
                     UpperCamelCase					 =		next_cell[3]
                     UpperCamelCase					 =		next_cell[1]

                     if x == goal[0] and y == goal[1]:
                            UpperCamelCase					 =		True
                     else:
                            for i in range(len(UpperCAmelCase_				)				):  # to try out different valid actions
                                   UpperCamelCase					 =		x + DIRECTIONS[i][0]
                                   UpperCamelCase					 =		y + DIRECTIONS[i][1]
                                   if xa >= 0 and xa < len(UpperCAmelCase_				) and ya >= 0 and ya < len(grid[0]				):
                                          if closed[xa][ya] == 0 and grid[xa][ya] == 0:
                                                 UpperCamelCase					 =		g + cost
                                                 UpperCamelCase					 =		ga + heuristic[xa][ya]
                                                 cell.append([fa, ga, xa, ya]				)
                                                 UpperCamelCase					 =		1
                                                 UpperCamelCase					 =		i
       UpperCamelCase					 =		[]
       UpperCamelCase					 =		goal[0]
       UpperCamelCase					 =		goal[1]
       invpath.append([x, y]				)  # we get the reverse path from here
       while x != init[0] or y != init[1]:
              UpperCamelCase					 =		x - DIRECTIONS[action[x][y]][0]
              UpperCamelCase					 =		y - DIRECTIONS[action[x][y]][1]
              UpperCamelCase					 =		xa
              UpperCamelCase					 =		ya
              invpath.append([x, y]				)

       UpperCamelCase					 =		[]
       for i in range(len(UpperCAmelCase_				)				):
              path.append(invpath[len(UpperCAmelCase_				) - 1 - i]				)
       return path, action


if __name__ == "__main__":
      SCREAMING_SNAKE_CASE      =     [
          [0, 1, 0, 0, 0, 0],
          [0, 1, 0, 0, 0, 0],  # 0 are free path whereas 1's are obstacles
          [0, 1, 0, 0, 0, 0],
          [0, 1, 0, 0, 1, 0],
          [0, 0, 0, 0, 1, 0],
      ]

      SCREAMING_SNAKE_CASE      =     [0, 0]
      # all coordinates are given in format [y,x]
      SCREAMING_SNAKE_CASE      =     [len(grid) - 1, len(grid[0]) - 1]
      SCREAMING_SNAKE_CASE      =     1

      # the cost map which pushes the path closer to the goal
      SCREAMING_SNAKE_CASE      =     [[0 for row in range(len(grid[0]))] for col in range(len(grid))]
      for i in range(len(grid)):
            for j in range(len(grid[0])):
                  SCREAMING_SNAKE_CASE      =     abs(i - goal[0]) + abs(j - goal[1])
                  if grid[i][j] == 1:
                        # added extra penalty in the heuristic map
                        SCREAMING_SNAKE_CASE      =     99

      SCREAMING_SNAKE_CASE     ,      SCREAMING_SNAKE_CASE      =     search(grid, init, goal, cost, heuristic)

      print("""ACTION MAP""")
      for i in range(len(action)):
            print(action[i])

      for i in range(len(path)):
            print(path[i])







"""simple docstring"""


from __future__ import annotations

from typing import Generic, TypeVar

SCREAMING_SNAKE_CASE      =     TypeVar("""T""")



class   __a  (      Generic[T]	):






       def __init__(  self :							List[Any]       ,      UpperCAmelCase_ :							T			)->  None:







              """simple docstring"""
              UpperCamelCase					 =		data
              UpperCamelCase					 =		self
              UpperCamelCase					 =		0





class   __a  (      Generic[T]	):






       def __init__(  self :							int			)->  None:







              """simple docstring"""
              # map from node name to the node object
              UpperCamelCase					 =		{}






       def 	_SCREAMING_SNAKE_CASE       (  self :							Optional[int]       ,      UpperCAmelCase_ :							T			)->  None:







              """simple docstring"""
              # create a new set with x as its member
              UpperCamelCase					 =		DisjointSetTreeNode(UpperCAmelCase_			)






       def 	_SCREAMING_SNAKE_CASE       (  self :							Optional[Any]       ,      UpperCAmelCase_ :							T			)->  DisjointSetTreeNode[T]:







              """simple docstring"""
              # find the set x belongs to (with path-compression)
              UpperCamelCase					 =		self.map[data]
              if elem_ref != elem_ref.parent:
                     UpperCamelCase					 =		self.find_set(elem_ref.parent.data			)
              return elem_ref.parent






       def 	_SCREAMING_SNAKE_CASE       (  self :							Any       ,      UpperCAmelCase_ :							DisjointSetTreeNode[T]       ,      UpperCAmelCase_ :							DisjointSetTreeNode[T]			)->  None:







              """simple docstring"""
              # helper function for union operation
              if nodea.rank > nodea.rank:
                     UpperCamelCase					 =		nodea
              else:
                     UpperCamelCase					 =		nodea
                     if nodea.rank == nodea.rank:
                            nodea.rank += 1






       def 	_SCREAMING_SNAKE_CASE       (  self :							int       ,      UpperCAmelCase_ :							T       ,      UpperCAmelCase_ :							T			)->  None:







              """simple docstring"""
              # merge 2 disjoint sets
              self.link(self.find_set(UpperCAmelCase_			)       ,      self.find_set(UpperCAmelCase_			)			)





class   __a  (      Generic[T]	):






       def __init__(  self :							Dict			)->  None:







              """simple docstring"""
              # connections: map from the node to the neighbouring nodes (with weights)
              UpperCamelCase					 =		{}






       def 	_SCREAMING_SNAKE_CASE       (  self :							Any       ,      UpperCAmelCase_ :							T			)->  None:







              """simple docstring"""
              # add a node ONLY if its not present in the graph
              if node not in self.connections:
                     UpperCamelCase					 =		{}






       def 	_SCREAMING_SNAKE_CASE       (  self :							Optional[Any]       ,      UpperCAmelCase_ :							T       ,      UpperCAmelCase_ :							T       ,      UpperCAmelCase_ :							int			)->  None:







              """simple docstring"""
              # add an edge with the given weight
              self.add_node(UpperCAmelCase_			)
              self.add_node(UpperCAmelCase_			)
              UpperCamelCase					 =		weight
              UpperCamelCase					 =		weight






       def 	_SCREAMING_SNAKE_CASE       (  self :							Tuple			)->  GraphUndirectedWeighted[T]:







              """simple docstring"""
              UpperCamelCase					 =		[]
              UpperCamelCase					 =		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 UpperCAmelCase_			: x[2]			)

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

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





