


from __future__ import annotations

UpperCAmelCase    =					list[tuple[int, int]]

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

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







class lowerCAmelCase_		:

 '''simple docstring'''

 def __init__(			self	,   _UpperCAmelCase	,   _UpperCAmelCase	,   _UpperCAmelCase	,   _UpperCAmelCase	,   _UpperCAmelCase	,   _UpperCAmelCase	,   ):
       snake_case_ =   pos_x
       snake_case_ =   pos_y
       snake_case_ =   (pos_y, pos_x)
       snake_case_ =   goal_x
       snake_case_ =   goal_y
       snake_case_ =   g_cost
       snake_case_ =   parent
       snake_case_ =   self.calculate_heuristic()



 def 		UpperCamelCase__  (			self      ):
       snake_case_ =   abs(self.pos_x - self.goal_x      )
       snake_case_ =   abs(self.pos_y - self.goal_y      )
       return dx + dy





 def __lt__(			self	,   _UpperCAmelCase      ):
       return self.f_cost < other.f_cost







class lowerCAmelCase_		:

 '''simple docstring'''

 def __init__(			self	,   _UpperCAmelCase	,   _UpperCAmelCase      ):
       snake_case_ =   Node(start[1]	,   start[0]	,   goal[1]	,   goal[0]	,   0	,   _UpperCAmelCase      )
       snake_case_ =   Node(goal[1]	,   goal[0]	,   goal[1]	,   goal[0]	,   9_99_99	,   _UpperCAmelCase      )

       snake_case_ =   [self.start]
       snake_case_ =   []

       snake_case_ =   False



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

             if current_node.pos == self.target.pos:
                   snake_case_ =   True
                   return self.retrace_path(_UpperCAmelCase      )

             self.closed_nodes.append(_UpperCAmelCase      )
             snake_case_ =   self.get_successors(_UpperCAmelCase      )

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

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

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



 def 		UpperCamelCase__  (			self	,   _UpperCAmelCase      ):
       snake_case_ =   []
       for action in delta:
             snake_case_ =   parent.pos_x + action[1]
             snake_case_ =   parent.pos_y + action[0]

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

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

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





 def 		UpperCamelCase__  (			self	,   _UpperCAmelCase      ):
       snake_case_ =   node
       snake_case_ =   []
       while current_node is not None:
             path.append((current_node.pos_y, current_node.pos_x)      )
             snake_case_ =   current_node.parent
       path.reverse()
       return path


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

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

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

      for elem in grid:
         print(elem)



def  __lowerCAmelCase					(SCREAMING_SNAKE_CASE      )->						int:




      """simple docstring"""

      assert column_title.isupper()
      snake_case_ =   0
      snake_case_ =   len(SCREAMING_SNAKE_CASE      ) - 1
      snake_case_ =   0

      while index >= 0:
            snake_case_ =   (ord(column_title[index]      ) - 64) * pow(26      ,      SCREAMING_SNAKE_CASE      )
            answer += value
            power += 1
            index -= 1

      return answer


if __name__ == "__main__":
   from doctest import testmod

   testmod()