import heapq
import sys

import numpy as np

__a  :     Optional[int]       =  tuple[int, int]




class    _UpperCamelCase      :


			"""simple docstring"""






			def __init__(   self						)     ->					Any:

							'''simple docstring'''


							__lowercase 			=							[]
							__lowercase 			=							set()





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

							'''simple docstring'''


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





			def        _SCREAMING_SNAKE_CASE			(   self						)     ->					Tuple:

							'''simple docstring'''


							return len(self.elements						) == 0





			def        _SCREAMING_SNAKE_CASE			(   self      ,   lowerCAmelCase__      ,   lowerCAmelCase__						)     ->					List[Any]:

							'''simple docstring'''


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





			def        _SCREAMING_SNAKE_CASE			(   self      ,   lowerCAmelCase__						)     ->					Any:

							'''simple docstring'''


							if item in self.set:
											self.set.remove(lowerCAmelCase__						)
											__lowercase 			=							[]
											((__lowercase)			,     (__lowercase)) 			=							heapq.heappop(self.elements						)
											while x != item:
															temp.append((pro, x)						)
															((__lowercase)			,     (__lowercase)) 			=							heapq.heappop(self.elements						)
											for prito, yyy in temp:
															heapq.heappush(self.elements      ,   (prito, yyy)						)





			def        _SCREAMING_SNAKE_CASE			(   self						)     ->					List[Any]:

							'''simple docstring'''


							return self.elements[0][1]





			def        _SCREAMING_SNAKE_CASE			(   self						)     ->					List[Any]:

							'''simple docstring'''


							((__lowercase)			,     (__lowercase)) 			=							heapq.heappop(self.elements						)
							self.set.remove(lowerCAmelCase__						)
							return (priority, item)





def 				UpperCAmelCase						(    lowercase							,			lowercase							):







				"""simple docstring"""



				__lowercase 			=							np.array(lowercase							)
				__lowercase 			=							np.array(lowercase							)
				return np.linalg.norm(a - b							)





def 				UpperCAmelCase						(    lowercase							,			lowercase							):







				"""simple docstring"""



				return consistent_heuristic(lowercase							,			lowercase							) // t





def 				UpperCAmelCase						(    lowercase							,			lowercase							):







				"""simple docstring"""



				return abs(p[0] - goal[0]							) + abs(p[1] - goal[1]							)





def 				UpperCAmelCase						(    lowercase							,			lowercase							,			lowercase							,			lowercase							):







				"""simple docstring"""



				__lowercase 			=							g_function[start] + Wa * heuristics[i](lowercase							,			lowercase							)
				return ans





def 				UpperCAmelCase						(    lowercase							,			lowercase							,			lowercase							):







				"""simple docstring"""



				__lowercase 			=							np.chararray((n, n)							)
				for i in range(lowercase							):
								for j in range(lowercase							):
												__lowercase 			=							'''*'''

				for i in range(lowercase							):
								for j in range(lowercase							):
												if (j, (n - 1) - i) in blocks:
																__lowercase 			=							'''#'''

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

				for i in range(lowercase							):
								for j in range(lowercase							):
												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:-'''							)
				__lowercase 			=							back_pointer[goal]
				while x != start:
								print(lowercase							,			end=''' '''							)
								__lowercase 			=							back_pointer[x]
				print(lowercase							)
				sys.exit()





def 				UpperCAmelCase						(    lowercase							):







				"""simple docstring"""



				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						(    lowercase							,			lowercase							,			lowercase							,			lowercase							,			lowercase							,			lowercase							,			lowercase							,			lowercase							,			):







				"""simple docstring"""



				for itera in range(lowercase							):
								open_list[itera].remove_element(lowercase							)
				# print("s", s)
				# print("j", j)
				((__lowercase)			,     (__lowercase)) 			=							s
				__lowercase 			=							(x - 1, y)
				__lowercase 			=							(x + 1, y)
				__lowercase 			=							(x, y + 1)
				__lowercase 			=							(x, y - 1)

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

												if valid(lowercase							) and g_function[neighbours] > g_function[s] + 1:
																__lowercase 			=							g_function[s] + 1
																__lowercase 			=							s
																if neighbours not in close_list_anchor:
																				open_list[0].put(lowercase							,			key(lowercase							,			0							,			lowercase							,			lowercase							)							)
																				if neighbours not in close_list_inad:
																								for var in range(1							,			lowercase							):
																												if key(lowercase							,			lowercase							,			lowercase							,			lowercase							) <= Wa * key(
																												    lowercase							,			0							,			lowercase							,			lowercase							):
																																open_list[j].put(
																																    lowercase							,			key(lowercase							,			lowercase							,			lowercase							,			lowercase							)							)





def 				UpperCAmelCase						(    ):







				"""simple docstring"""



				__lowercase 			=							[]
				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


__a  :     Any       =  {0: consistent_heuristic, 1: heuristic_a, 2: heuristic_a}

__a  :     List[str]       =  [
    (0, 1),
    (1, 1),
    (2, 1),
    (3, 1),
    (4, 1),
    (5, 1),
    (6, 1),
    (7, 1),
    (8, 1),
    (9, 1),
    (1_0, 1),
    (1_1, 1),
    (1_2, 1),
    (1_3, 1),
    (1_4, 1),
    (1_5, 1),
    (1_6, 1),
    (1_7, 1),
    (1_8, 1),
    (1_9, 1),
]
__a  :     int       =  make_common_ground()


__a  :     Tuple       =  blocks_blk
# hyper parameters
__a  :     List[str]       =  1
__a  :     int       =  1
__a  :     Optional[int]       =  2_0
__a  :     Optional[int]       =  3  # one consistent and two other inconsistent

# start and end destination
__a  :     Optional[Any]       =  (0, 0)
__a  :     List[str]       =  (n - 1, n - 1)

__a  :     Tuple       =  1





def 				UpperCAmelCase						(    lowercase							,			lowercase							,			lowercase							):







				"""simple docstring"""



				__lowercase 			=							{start: 0, goal: float('''inf'''							)}
				__lowercase 			=							{start: -1, goal: -1}
				__lowercase 			=							[]
				__lowercase 			=							set()

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

				__lowercase 			=							[]
				__lowercase 			=							[]
				while open_list[0].minkey() < float('''inf'''							):
								for i in range(1							,			lowercase							):
												# 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(lowercase							,			lowercase							,			lowercase							)
																else:
																				__lowercase			,     __lowercase 			=							open_list[i].top_show()
																				visited.add(lowercase							)
																				expand_state(
																				    lowercase							,			lowercase							,			lowercase							,			lowercase							,			lowercase							,			lowercase							,			lowercase							,			lowercase							,			)
																				close_list_inad.append(lowercase							)
												else:
																if g_function[goal] <= open_list[0].minkey():
																				if g_function[goal] < float('''inf'''							):
																								do_something(lowercase							,			lowercase							,			lowercase							)
																else:
																				__lowercase 			=							open_list[0].top_show()
																				visited.add(lowercase							)
																				expand_state(
																				    lowercase							,			0							,			lowercase							,			lowercase							,			lowercase							,			lowercase							,			lowercase							,			lowercase							,			)
																				close_list_anchor.append(lowercase							)
				print('''No path found to goal'''							)
				print()
				for i in range(n - 1							,			-1							,			-1							):
								for j in range(lowercase							):
												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)
import warnings
from functools import wraps
from typing import Callable





def 				UpperCAmelCase						(    lowercase							):







				"""simple docstring"""



				@wraps(lowercase							)
				def _inner_fn(*lowercase							,			**lowercase							):
								warnings.warn(
								    (F"'{fn.__name__}' is experimental and might be subject to breaking changes in the future.")							,			lowercase							,			)
								return fn(*lowercase							,			**lowercase							)

				return _inner_fn