

'''simple docstring'''







import heapq
import sys

import numpy as np

__lowerCamelCase						    =      tuple[int, int]


class    A__ :



    def __init__(   self    )  -> int:





           '''simple docstring'''
           A_		   = []
           A_		   = set()



    def    snake_case_     (   self    )  -> Optional[Any]:





           '''simple docstring'''
           if not self.empty():
                  return self.elements[0][0]
           else:
                  return float("""inf"""    )



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





           '''simple docstring'''
           return len(self.elements    ) == 0



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





           '''simple docstring'''
           if item not in self.set:
                  heapq.heappush(self.elements						,			(priority, item)    )
                  self.set.add(UpperCamelCase__    )
           else:
                  # update
                  # print("update", item)
                  A_		   = []
                  ((A_)   ,     (A_))		   = heapq.heappop(self.elements    )
                  while x != item:
                         temp.append((pri, x)    )
                         ((A_)   ,     (A_))		   = heapq.heappop(self.elements    )
                  temp.append((priority, item)    )
                  for pro, xxx in temp:
                         heapq.heappush(self.elements						,			(pro, xxx)    )



    def    snake_case_     (   self						,			UpperCamelCase__    )  -> Any:





           '''simple docstring'''
           if item in self.set:
                  self.set.remove(UpperCamelCase__    )
                  A_		   = []
                  ((A_)   ,     (A_))		   = heapq.heappop(self.elements    )
                  while x != item:
                         temp.append((pro, x)    )
                         ((A_)   ,     (A_))		   = heapq.heappop(self.elements    )
                  for prito, yyy in temp:
                         heapq.heappush(self.elements						,			(prito, yyy)    )



    def    snake_case_     (   self    )  -> List[str]:





           '''simple docstring'''
           return self.elements[0][1]







    def    snake_case_     (   self    )  -> Dict:





           '''simple docstring'''
           ((A_)   ,     (A_))		   = heapq.heappop(self.elements    )
           self.set.remove(UpperCamelCase__    )
           return (priority, item)

def  UpperCAmelCase__      ( UpperCAmelCase__,    UpperCAmelCase__			)     ->     List[str]:
       # euclidean distance
       A_		   = np.array(UpperCAmelCase__			)
       A_		   = np.array(UpperCAmelCase__			)
       return np.linalg.norm(a - b			)
def  UpperCAmelCase__      ( UpperCAmelCase__,    UpperCAmelCase__			)     ->     List[Any]:
       # integer division by time variable
       return consistent_heuristic(UpperCAmelCase__,    UpperCAmelCase__			) // t
def  UpperCAmelCase__      ( UpperCAmelCase__,    UpperCAmelCase__			)     ->     List[str]:
       # manhattan distance
       return abs(p[0] - goal[0]			) + abs(p[1] - goal[1]			)
def  UpperCAmelCase__      ( UpperCAmelCase__,    UpperCAmelCase__,    UpperCAmelCase__,    UpperCAmelCase__			)     ->     List[str]:
       A_		   = g_function[start] + Wa * heuristics[i](UpperCAmelCase__,    UpperCAmelCase__			)
       return ans
def  UpperCAmelCase__      ( UpperCAmelCase__,    UpperCAmelCase__,    UpperCAmelCase__			)     ->     Optional[Any]:
       A_		   = np.chararray((n, n)			)
       for i in range(UpperCAmelCase__			):
              for j in range(UpperCAmelCase__			):
                     A_		   = """*"""

       for i in range(UpperCAmelCase__			):
              for j in range(UpperCAmelCase__			):
                     if (j, (n - 1) - i) in blocks:
                            A_		   = """#"""

       A_		   = """-"""
       A_		   = back_pointer[goal]
       while x != start:
              ((A_)   ,     (A_))		   = x
              # print(x)
              A_		   = """-"""
              A_		   = back_pointer[x]
       A_		   = """-"""

       for i in range(UpperCAmelCase__			):
              for j in range(UpperCAmelCase__			):
                     if (i, j) == (0, n - 1):
                            print(grid[i][j],    end=""" """			)
                            print("""<-- End position""",    end=""" """			)
                     else:
                            print(grid[i][j],    end=""" """			)
              print()
       print("""^"""			)
       print("""Start position"""			)
       print()
       print("""# is an obstacle"""			)
       print("""- is the path taken by algorithm"""			)
       print("""PATH TAKEN BY THE ALGORITHM IS:-"""			)
       A_		   = back_pointer[goal]
       while x != start:
              print(UpperCAmelCase__,    end=""" """			)
              A_		   = back_pointer[x]
       print(UpperCAmelCase__			)
       sys.exit()
def  UpperCAmelCase__      ( UpperCAmelCase__			)     ->     Optional[Any]:
       if p[0] < 0 or p[0] > n - 1:
              return False
       if p[1] < 0 or p[1] > n - 1:
              return False
       return True
def  UpperCAmelCase__      ( UpperCAmelCase__,    UpperCAmelCase__,    UpperCAmelCase__,    UpperCAmelCase__,    UpperCAmelCase__,    UpperCAmelCase__,    UpperCAmelCase__,    UpperCAmelCase__,    )     ->     int:
       for itera in range(UpperCAmelCase__			):
              open_list[itera].remove_element(UpperCAmelCase__			)
       # print("s", s)
       # print("j", j)
       ((A_)   ,     (A_))		   = s
       A_		   = (x - 1, y)
       A_		   = (x + 1, y)
       A_		   = (x, y + 1)
       A_		   = (x, y - 1)

       for neighbours in [left, right, up, down]:
              if neighbours not in blocks:
                     if valid(UpperCAmelCase__			) and neighbours not in visited:
                            # print("neighbour", neighbours)
                            visited.add(UpperCAmelCase__			)
                            A_		   = -1
                            A_		   = float("""inf"""			)

                     if valid(UpperCAmelCase__			) and g_function[neighbours] > g_function[s] + 1:
                            A_		   = g_function[s] + 1
                            A_		   = s
                            if neighbours not in close_list_anchor:
                                   open_list[0].put(UpperCAmelCase__,    key(UpperCAmelCase__,    0,    UpperCAmelCase__,    UpperCAmelCase__			)			)
                                   if neighbours not in close_list_inad:
                                          for var in range(1,    UpperCAmelCase__			):
                                                 if key(UpperCAmelCase__,    UpperCAmelCase__,    UpperCAmelCase__,    UpperCAmelCase__			) <= Wa * key(
                                                     UpperCAmelCase__,    0,    UpperCAmelCase__,    UpperCAmelCase__			):
                                                        open_list[j].put(
                                                            UpperCAmelCase__,    key(UpperCAmelCase__,    UpperCAmelCase__,    UpperCAmelCase__,    UpperCAmelCase__			)			)
def  UpperCAmelCase__      ( )     ->     Any:
       A_		   = []
       for x in range(1,    5			):
              for y in range(1,    6			):
                     some_list.append((x, y)			)

       for x in range(15,    20			):
              some_list.append((x, 17)			)

       for x in range(10,    19			):
              for y in range(1,    15			):
                     some_list.append((x, y)			)

    # L block
       for x in range(1,    4			):
              for y in range(12,    19			):
                     some_list.append((x, y)			)
       for x in range(3,    13			):
              for y in range(16,    19			):
                     some_list.append((x, y)			)
       return some_list


__lowerCamelCase						    =      {0: consistent_heuristic, 1: heuristic_a, 2: heuristic_a}

__lowerCamelCase						    =      [
    (0, 1),
    (1, 1),
    (2, 1),
    (3, 1),
    (4, 1),
    (5, 1),
    (6, 1),
    (7, 1),
    (8, 1),
    (9, 1),
    (10, 1),
    (11, 1),
    (12, 1),
    (13, 1),
    (14, 1),
    (15, 1),
    (16, 1),
    (17, 1),
    (18, 1),
    (19, 1),
]
__lowerCamelCase						    =      make_common_ground()


__lowerCamelCase						    =      blocks_blk
# hyper parameters
__lowerCamelCase						    =      1
__lowerCamelCase						    =      1
__lowerCamelCase						    =      20
__lowerCamelCase						    =      3  # one consistent and two other inconsistent

# start and end destination
__lowerCamelCase						    =      (0, 0)
__lowerCamelCase						    =      (n - 1, n - 1)

__lowerCamelCase						    =      1
def  UpperCAmelCase__      ( UpperCAmelCase__,    UpperCAmelCase__,    UpperCAmelCase__			)     ->     int:
       A_		   = {start: 0, goal: float("""inf"""			)}
       A_		   = {start: -1, goal: -1}
       A_		   = []
       A_		   = set()

       for i in range(UpperCAmelCase__			):
              open_list.append(PriorityQueue()			)
              open_list[i].put(UpperCAmelCase__,    key(UpperCAmelCase__,    UpperCAmelCase__,    UpperCAmelCase__,    UpperCAmelCase__			)			)

       A_		   = []
       A_		   = []
       while open_list[0].minkey() < float("""inf"""			):
              for i in range(1,    UpperCAmelCase__			):
                     # print(open_list[0].minkey(), open_list[i].minkey())
                     if open_list[i].minkey() <= Wa * open_list[0].minkey():
                            global t
                            t += 1
                            if g_function[goal] <= open_list[i].minkey():
                                   if g_function[goal] < float("""inf"""			):
                                          do_something(UpperCAmelCase__,    UpperCAmelCase__,    UpperCAmelCase__			)
                            else:
                                   A_   ,     A_		   = open_list[i].top_show()
                                   visited.add(UpperCAmelCase__			)
                                   expand_state(
                                       UpperCAmelCase__,    UpperCAmelCase__,    UpperCAmelCase__,    UpperCAmelCase__,    UpperCAmelCase__,    UpperCAmelCase__,    UpperCAmelCase__,    UpperCAmelCase__,    )
                                   close_list_inad.append(UpperCAmelCase__			)
                     else:
                            if g_function[goal] <= open_list[0].minkey():
                                   if g_function[goal] < float("""inf"""			):
                                          do_something(UpperCAmelCase__,    UpperCAmelCase__,    UpperCAmelCase__			)
                            else:
                                   A_		   = open_list[0].top_show()
                                   visited.add(UpperCAmelCase__			)
                                   expand_state(
                                       UpperCAmelCase__,    0,    UpperCAmelCase__,    UpperCAmelCase__,    UpperCAmelCase__,    UpperCAmelCase__,    UpperCAmelCase__,    UpperCAmelCase__,    )
                                   close_list_anchor.append(UpperCAmelCase__			)
       print("""No path found to goal"""			)
       print()
       for i in range(n - 1,    -1,    -1			):
              for j in range(UpperCAmelCase__			):
                     if (j, i) in blocks:
                            print("""#""",    end=""" """			)
                     elif (j, i) in back_pointer:
                            if (j, i) == (n - 1, n - 1):
                                   print("""*""",    end=""" """			)
                            else:
                                   print("""-""",    end=""" """			)
                     else:
                            print("""*""",    end=""" """			)
                     if (j, i) == (n - 1, n - 1):
                            print("""<-- End position""",    end=""" """			)
              print()
       print("""^"""			)
       print("""Start position"""			)
       print()
       print("""# is an obstacle"""			)
       print("""- is the path taken by algorithm"""			)


if __name__ == "__main__":
      multi_a_star(start, goal, n_heuristic)



'''simple docstring'''







def  UpperCAmelCase__      ( UpperCAmelCase__ = 10_00			)     ->     int:
       return sum(2 * a * ((a - 1) // 2) for a in range(3,    n + 1			)			)


if __name__ == "__main__":
      print(solution())
