


'''simple docstring'''


import heapq
import sys

import numpy as np

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





class        lowercase__    :





							'''simple docstring'''


							def __init__(       self    ):
											_SCREAMING_SNAKE_CASE					:			Tuple							= []
											_SCREAMING_SNAKE_CASE					:			Tuple							= set()






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






							def UpperCAmelCase_      (       self    ):
											return len(self.elements    ) == 0






							def UpperCAmelCase_      (       self       ,   __snake_case       ,   __snake_case    ):
											if item not in self.set:
															heapq.heappush(self.elements       ,   (priority, item)    )
															self.set.add(__snake_case    )
											else:
															# update
															# print("update", item)
															_SCREAMING_SNAKE_CASE					:			List[Any]							= []
															((_SCREAMING_SNAKE_CASE)						,			(_SCREAMING_SNAKE_CASE))					:			List[str]							= heapq.heappop(self.elements    )
															while x != item:
																			temp.append((pri, x)    )
																			((_SCREAMING_SNAKE_CASE)						,			(_SCREAMING_SNAKE_CASE))					:			Union[str, Any]							= heapq.heappop(self.elements    )
															temp.append((priority, item)    )
															for pro, xxx in temp:
																			heapq.heappush(self.elements       ,   (pro, xxx)    )






							def UpperCAmelCase_      (       self       ,   __snake_case    ):
											if item in self.set:
															self.set.remove(__snake_case    )
															_SCREAMING_SNAKE_CASE					:			Optional[int]							= []
															((_SCREAMING_SNAKE_CASE)						,			(_SCREAMING_SNAKE_CASE))					:			Union[str, Any]							= heapq.heappop(self.elements    )
															while x != item:
																			temp.append((pro, x)    )
																			((_SCREAMING_SNAKE_CASE)						,			(_SCREAMING_SNAKE_CASE))					:			Union[str, Any]							= heapq.heappop(self.elements    )
															for prito, yyy in temp:
																			heapq.heappush(self.elements       ,   (prito, yyy)    )






							def UpperCAmelCase_      (       self    ):
											return self.elements[0][1]






							def UpperCAmelCase_      (       self    ):
											((_SCREAMING_SNAKE_CASE)						,			(_SCREAMING_SNAKE_CASE))					:			int							= heapq.heappop(self.elements    )
											self.set.remove(__snake_case    )
											return (priority, item)







def      snake_case_  (    SCREAMING_SNAKE_CASE__				, SCREAMING_SNAKE_CASE__	):







				"""simple docstring"""





				_SCREAMING_SNAKE_CASE					:			int							= np.array(SCREAMING_SNAKE_CASE__	)
				_SCREAMING_SNAKE_CASE					:			List[str]							= np.array(SCREAMING_SNAKE_CASE__	)
				return np.linalg.norm(a - b	)







def      snake_case_  (    SCREAMING_SNAKE_CASE__				, SCREAMING_SNAKE_CASE__	):







				"""simple docstring"""





				return consistent_heuristic(SCREAMING_SNAKE_CASE__				, SCREAMING_SNAKE_CASE__	) // t







def      snake_case_  (    SCREAMING_SNAKE_CASE__				, SCREAMING_SNAKE_CASE__	):







				"""simple docstring"""





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







def      snake_case_  (    SCREAMING_SNAKE_CASE__				, SCREAMING_SNAKE_CASE__				, SCREAMING_SNAKE_CASE__				, SCREAMING_SNAKE_CASE__	):







				"""simple docstring"""





				_SCREAMING_SNAKE_CASE					:			Optional[int]							= g_function[start] + Wa * heuristics[i](SCREAMING_SNAKE_CASE__				, SCREAMING_SNAKE_CASE__	)
				return ans







def      snake_case_  (    SCREAMING_SNAKE_CASE__				, SCREAMING_SNAKE_CASE__				, SCREAMING_SNAKE_CASE__	):







				"""simple docstring"""





				_SCREAMING_SNAKE_CASE					:			Tuple							= np.chararray((n, n)	)
				for i in range(SCREAMING_SNAKE_CASE__	):
								for j in range(SCREAMING_SNAKE_CASE__	):
												_SCREAMING_SNAKE_CASE					:			List[str]							= """*"""

				for i in range(SCREAMING_SNAKE_CASE__	):
								for j in range(SCREAMING_SNAKE_CASE__	):
												if (j, (n - 1) - i) in blocks:
																_SCREAMING_SNAKE_CASE					:			List[str]							= """#"""

				_SCREAMING_SNAKE_CASE					:			Tuple							= """-"""
				_SCREAMING_SNAKE_CASE					:			int							= back_pointer[goal]
				while x != start:
								((_SCREAMING_SNAKE_CASE)						,			(_SCREAMING_SNAKE_CASE))					:			str							= x
								# print(x)
								_SCREAMING_SNAKE_CASE					:			str							= """-"""
								_SCREAMING_SNAKE_CASE					:			Any							= back_pointer[x]
				_SCREAMING_SNAKE_CASE					:			Union[str, Any]							= """-"""

				for i in range(SCREAMING_SNAKE_CASE__	):
								for j in range(SCREAMING_SNAKE_CASE__	):
												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:-"""	)
				_SCREAMING_SNAKE_CASE					:			Union[str, Any]							= back_pointer[goal]
				while x != start:
								print(SCREAMING_SNAKE_CASE__				, end=""" """	)
								_SCREAMING_SNAKE_CASE					:			str							= back_pointer[x]
				print(SCREAMING_SNAKE_CASE__	)
				sys.exit()







def      snake_case_  (    SCREAMING_SNAKE_CASE__	):







				"""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      snake_case_  (    SCREAMING_SNAKE_CASE__				, SCREAMING_SNAKE_CASE__				, SCREAMING_SNAKE_CASE__				, SCREAMING_SNAKE_CASE__				, SCREAMING_SNAKE_CASE__				, SCREAMING_SNAKE_CASE__				, SCREAMING_SNAKE_CASE__				, SCREAMING_SNAKE_CASE__				, ):







				"""simple docstring"""





				for itera in range(SCREAMING_SNAKE_CASE__	):
								open_list[itera].remove_element(SCREAMING_SNAKE_CASE__	)
				# print("s", s)
				# print("j", j)
				((_SCREAMING_SNAKE_CASE)						,			(_SCREAMING_SNAKE_CASE))					:			int							= s
				_SCREAMING_SNAKE_CASE					:			Union[str, Any]							= (x - 1, y)
				_SCREAMING_SNAKE_CASE					:			Optional[int]							= (x + 1, y)
				_SCREAMING_SNAKE_CASE					:			List[str]							= (x, y + 1)
				_SCREAMING_SNAKE_CASE					:			Any							= (x, y - 1)

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

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







def      snake_case_  (    ):







				"""simple docstring"""





				_SCREAMING_SNAKE_CASE					:			Optional[int]							= []
				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


UpperCAmelCase_						:  Optional[int]				  =						{0: consistent_heuristic, 1: heuristic_a, 2: heuristic_a}

UpperCAmelCase_						:  Union[str, Any]				  =						[
    (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),
]
UpperCAmelCase_						:  Optional[int]				  =						make_common_ground()


UpperCAmelCase_						:  List[Any]				  =						blocks_blk
# hyper parameters
UpperCAmelCase_						:  Tuple				  =						1
UpperCAmelCase_						:  Any				  =						1
UpperCAmelCase_						:  Optional[int]				  =						20
UpperCAmelCase_						:  Optional[int]				  =						3  # one consistent and two other inconsistent

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

UpperCAmelCase_						:  Tuple				  =						1







def      snake_case_  (    SCREAMING_SNAKE_CASE__				, SCREAMING_SNAKE_CASE__				, SCREAMING_SNAKE_CASE__	):







				"""simple docstring"""





				_SCREAMING_SNAKE_CASE					:			Optional[int]							= {start: 0, goal: float("""inf"""	)}
				_SCREAMING_SNAKE_CASE					:			int							= {start: -1, goal: -1}
				_SCREAMING_SNAKE_CASE					:			Any							= []
				_SCREAMING_SNAKE_CASE					:			Union[str, Any]							= set()

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

				_SCREAMING_SNAKE_CASE					:			list[int]							= []
				_SCREAMING_SNAKE_CASE					:			list[int]							= []
				while open_list[0].minkey() < float("""inf"""	):
								for i in range(1				, SCREAMING_SNAKE_CASE__	):
												# 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(SCREAMING_SNAKE_CASE__				, SCREAMING_SNAKE_CASE__				, SCREAMING_SNAKE_CASE__	)
																else:
																				_SCREAMING_SNAKE_CASE						,			_SCREAMING_SNAKE_CASE					:			Optional[int]							= open_list[i].top_show()
																				visited.add(SCREAMING_SNAKE_CASE__	)
																				expand_state(
																				    SCREAMING_SNAKE_CASE__				, SCREAMING_SNAKE_CASE__				, SCREAMING_SNAKE_CASE__				, SCREAMING_SNAKE_CASE__				, SCREAMING_SNAKE_CASE__				, SCREAMING_SNAKE_CASE__				, SCREAMING_SNAKE_CASE__				, SCREAMING_SNAKE_CASE__				, )
																				close_list_inad.append(SCREAMING_SNAKE_CASE__	)
												else:
																if g_function[goal] <= open_list[0].minkey():
																				if g_function[goal] < float("""inf"""	):
																								do_something(SCREAMING_SNAKE_CASE__				, SCREAMING_SNAKE_CASE__				, SCREAMING_SNAKE_CASE__	)
																else:
																				_SCREAMING_SNAKE_CASE					:			str							= open_list[0].top_show()
																				visited.add(SCREAMING_SNAKE_CASE__	)
																				expand_state(
																				    SCREAMING_SNAKE_CASE__				, 0				, SCREAMING_SNAKE_CASE__				, SCREAMING_SNAKE_CASE__				, SCREAMING_SNAKE_CASE__				, SCREAMING_SNAKE_CASE__				, SCREAMING_SNAKE_CASE__				, SCREAMING_SNAKE_CASE__				, )
																				close_list_anchor.append(SCREAMING_SNAKE_CASE__	)
				print("""No path found to goal"""	)
				print()
				for i in range(n - 1				, -1				, -1	):
								for j in range(SCREAMING_SNAKE_CASE__	):
												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      snake_case_  (    SCREAMING_SNAKE_CASE__				, SCREAMING_SNAKE_CASE__	):







				"""simple docstring"""





				if b == 0:
								return 1
				if (b % 2) == 0:
								return actual_power(SCREAMING_SNAKE_CASE__				, int(b / 2	)	) * actual_power(SCREAMING_SNAKE_CASE__				, int(b / 2	)	)
				else:
								return a * actual_power(SCREAMING_SNAKE_CASE__				, int(b / 2	)	) * actual_power(SCREAMING_SNAKE_CASE__				, int(b / 2	)	)







def      snake_case_  (    SCREAMING_SNAKE_CASE__				, SCREAMING_SNAKE_CASE__	):







				"""simple docstring"""





				if b < 0:
								return 1 / actual_power(SCREAMING_SNAKE_CASE__				, SCREAMING_SNAKE_CASE__	)
				return actual_power(SCREAMING_SNAKE_CASE__				, SCREAMING_SNAKE_CASE__	)


if __name__ == "__main__":
				print(power(-2, -3))




