





from __future__ import annotations

__lowercase       :Optional[Any]       =  [
    [-1, 0],  # left
    [0, -1],  # down
    [1, 0],  # right
    [0, 1],  # up
]







def       UpperCAmelCase							(     _lowerCamelCase      :  list[list[int]]			,   _lowerCamelCase      :  list[int]			,   _lowerCamelCase      :  list[int]			,   _lowerCamelCase      :  int			,   _lowerCamelCase      :  list[list[int]]			,   ):





						'''simple docstring'''


						SCREAMING_SNAKE_CASE__     :				Any   =					[
						    [0 for col in range(len(grid[0]     )     )] for row in range(len(_lowerCamelCase     )     )
						]  # the reference grid
						SCREAMING_SNAKE_CASE__     :				Optional[int]   =					1
						SCREAMING_SNAKE_CASE__     :				Tuple   =					[
						    [0 for col in range(len(grid[0]     )     )] for row in range(len(_lowerCamelCase     )     )
						]  # the action grid

						SCREAMING_SNAKE_CASE__     :				List[str]   =					init[0]
						SCREAMING_SNAKE_CASE__     :				Optional[Any]   =					init[1]
						SCREAMING_SNAKE_CASE__     :				Dict   =					0
						SCREAMING_SNAKE_CASE__     :				Optional[int]   =					g + heuristic[x][y]  # cost from starting cell to destination cell
						SCREAMING_SNAKE_CASE__     :				List[Any]   =					[[f, g, x, y]]

						SCREAMING_SNAKE_CASE__     :				List[Any]   =					False  # flag that is set when search is complete
						SCREAMING_SNAKE_CASE__     :				Optional[Any]   =					False  # flag set if we can't find expand

						while not found and not resign:
												if len(_lowerCamelCase     ) == 0:
																		raise ValueError("Algorithm is unable to find solution"     )
												else:  # to choose the least costliest action so as to move closer to the goal
																		cell.sort()
																		cell.reverse()
																		SCREAMING_SNAKE_CASE__     :				Dict   =					cell.pop()
																		SCREAMING_SNAKE_CASE__     :				Any   =					next_cell[2]
																		SCREAMING_SNAKE_CASE__     :				str   =					next_cell[3]
																		SCREAMING_SNAKE_CASE__     :				str   =					next_cell[1]

																		if x == goal[0] and y == goal[1]:
																								SCREAMING_SNAKE_CASE__     :				Optional[int]   =					True
																		else:
																								for i in range(len(_lowerCamelCase     )     ):  # to try out different valid actions
																														SCREAMING_SNAKE_CASE__     :				List[Any]   =					x + DIRECTIONS[i][0]
																														SCREAMING_SNAKE_CASE__     :				List[Any]   =					y + DIRECTIONS[i][1]
																														if xa >= 0 and xa < len(_lowerCamelCase     ) and ya >= 0 and ya < len(grid[0]     ):
																																				if closed[xa][ya] == 0 and grid[xa][ya] == 0:
																																										SCREAMING_SNAKE_CASE__     :				Any   =					g + cost
																																										SCREAMING_SNAKE_CASE__     :				List[str]   =					ga + heuristic[xa][ya]
																																										cell.append([fa, ga, xa, ya]     )
																																										SCREAMING_SNAKE_CASE__     :				List[str]   =					1
																																										SCREAMING_SNAKE_CASE__     :				Optional[int]   =					i
						SCREAMING_SNAKE_CASE__     :				Tuple   =					[]
						SCREAMING_SNAKE_CASE__     :				str   =					goal[0]
						SCREAMING_SNAKE_CASE__     :				int   =					goal[1]
						invpath.append([x, y]     )  # we get the reverse path from here
						while x != init[0] or y != init[1]:
												SCREAMING_SNAKE_CASE__     :				int   =					x - DIRECTIONS[action[x][y]][0]
												SCREAMING_SNAKE_CASE__     :				Tuple   =					y - DIRECTIONS[action[x][y]][1]
												SCREAMING_SNAKE_CASE__     :				List[Any]   =					xa
												SCREAMING_SNAKE_CASE__     :				Optional[int]   =					ya
												invpath.append([x, y]     )

						SCREAMING_SNAKE_CASE__     :				Tuple   =					[]
						for i in range(len(_lowerCamelCase     )     ):
												path.append(invpath[len(_lowerCamelCase     ) - 1 - i]     )
						return path, action


if __name__ == "__main__":
				__lowercase       :int       =  [
				    [0, 1, 0, 0, 0, 0],
				    [0, 1, 0, 0, 0, 0],  # 0 are free path whereas 1's are obstacles
				    [0, 1, 0, 0, 0, 0],
				    [0, 1, 0, 0, 1, 0],
				    [0, 0, 0, 0, 1, 0],
				]

				__lowercase       :List[str]       =  [0, 0]
				# all coordinates are given in format [y,x]
				__lowercase       :Union[str, Any]       =  [len(grid) - 1, len(grid[0]) - 1]
				__lowercase       :Optional[Any]       =  1

				# the cost map which pushes the path closer to the goal
				__lowercase       :List[str]       =  [[0 for row in range(len(grid[0]))] for col in range(len(grid))]
				for i in range(len(grid)):
								for j in range(len(grid[0])):
												__lowercase       :Optional[int]       =  abs(i - goal[0]) + abs(j - goal[1])
												if grid[i][j] == 1:
																# added extra penalty in the heuristic map
																__lowercase       :str       =  99

				__lowercase       ,     __lowercase       :Optional[int]       =  search(grid, init, goal, cost, heuristic)

				print("ACTION MAP")
				for i in range(len(action)):
								print(action[i])

				for i in range(len(path)):
								print(path[i])






from __future__ import annotations







def       UpperCAmelCase							(     _lowerCamelCase      :  list			,   _lowerCamelCase      :  int | None = None			,   _lowerCamelCase      :  int | None = None     ):





						'''simple docstring'''


						if start is None:
												SCREAMING_SNAKE_CASE__     :				Union[str, Any]   =					0

						if end is None:
												SCREAMING_SNAKE_CASE__     :				Any   =					len(_lowerCamelCase     ) - 1

						if start >= end:
												return

						SCREAMING_SNAKE_CASE__     :				List[str]   =					(start + end) // 2

						slowsort(_lowerCamelCase			,   _lowerCamelCase			,   _lowerCamelCase     )
						slowsort(_lowerCamelCase			,   mid + 1			,   _lowerCamelCase     )

						if sequence[end] < sequence[mid]:
												SCREAMING_SNAKE_CASE__,							SCREAMING_SNAKE_CASE__     :				Optional[int]   =					sequence[mid], sequence[end]

						slowsort(_lowerCamelCase			,   _lowerCamelCase			,   end - 1     )


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

				testmod()