





from __future__ import annotations

lowercase_          =		list[tuple[int, int]]

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

lowercase_          =		([-1, 0], [0, -1], [1, 0], [0, 1])  # up, left, down, right
class     SCREAMING_SNAKE_CASE       :


   def __init__(   self      :    int      ,					a      :    Union[str, Any]      ,					a      :    Any      ,					a      :    List[str]      ,					a      :    List[Any]      ,					a      :    Optional[int]      ,					a      :    str      ,					)->       List[Any]:





     """simple docstring"""







     lowercase__           =  pos_x
     lowercase__           =  pos_y
     lowercase__           =  (pos_y, pos_x)
     lowercase__           =  goal_x
     lowercase__           =  goal_y
     lowercase__           =  g_cost
     lowercase__           =  parent
     lowercase__           =  self.calculate_heuristic()


   def 	SCREAMING_SNAKE_CASE_							(   self      :    Union[str, Any]	)->       Any:





     """simple docstring"""







     lowercase__           =  abs(self.pos_x - self.goal_x	)
     lowercase__           =  abs(self.pos_y - self.goal_y	)
     return dx + dy


   def __lt__(   self      :    List[Any]      ,					a      :    int	)->       Tuple:





     """simple docstring"""







     return self.f_cost < other.f_cost






class     SCREAMING_SNAKE_CASE       :


   def __init__(   self      :    Any      ,					a      :    str      ,					a      :    int	)->       List[str]:





     """simple docstring"""







     lowercase__           =  Node(start[1]      ,					start[0]      ,					goal[1]      ,					goal[0]      ,					0      ,					__SCREAMING_SNAKE_CASE	)
     lowercase__           =  Node(goal[1]      ,					goal[0]      ,					goal[1]      ,					goal[0]      ,					99_999      ,					__SCREAMING_SNAKE_CASE	)

     lowercase__           =  [self.start]
     lowercase__           =  []

     lowercase__           =  False


   def 	SCREAMING_SNAKE_CASE_							(   self      :    List[str]	)->       Tuple:





     """simple docstring"""







     while self.open_nodes:
       # Open Nodes are sorted using __lt__
       self.open_nodes.sort()
       lowercase__           =  self.open_nodes.pop(0	)

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

       self.closed_nodes.append(__SCREAMING_SNAKE_CASE	)
       lowercase__           =  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
           lowercase__           =  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 	SCREAMING_SNAKE_CASE_							(   self      :    int      ,					a      :    Any	)->       str:





     """simple docstring"""







     lowercase__           =  []
     for action in delta:
       lowercase__           =  parent.pos_x + action[1]
       lowercase__           =  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 	SCREAMING_SNAKE_CASE_							(   self      :    List[str]      ,					a      :    List[Any]	)->       int:





     """simple docstring"""







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


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

      print("""------""")

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

            for elem in grid:
                  print(elem)









def       __UpperCamelCase  (_SCREAMING_SNAKE_CASE		,						_SCREAMING_SNAKE_CASE		,						_SCREAMING_SNAKE_CASE		)    ->       int:

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




def       __UpperCamelCase  (_SCREAMING_SNAKE_CASE = 1777		,						_SCREAMING_SNAKE_CASE = 1855		,						_SCREAMING_SNAKE_CASE = 8		)    ->       int:
  lowercase__           =  base
  for _ in range(1		,						_SCREAMING_SNAKE_CASE		):
    lowercase__           =  _modexpt(_SCREAMING_SNAKE_CASE		,						_SCREAMING_SNAKE_CASE		,						10**digits		)

  return result


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


