





'''simple docstring'''


from __future__ import annotations

lowerCAmelCase_   :   Optional[int]       =					[
    [-1, 0],  # left
    [0, -1],  # down
    [1, 0],  # right
    [0, 1],  # up
]







def    _lowerCamelCase  (__lowerCamelCase  :     list[list[int]]					,  __lowerCamelCase  :     list[int]					,  __lowerCamelCase  :     list[int]					,  __lowerCamelCase  :     int					,  __lowerCamelCase  :     list[list[int]]					,  )   ->    tuple[list[list[int]], list[list[int]]]:
			a__     = [
			    [0 for col in range(len(grid[0]     )     )] for row in range(len(SCREAMING_SNAKE_CASE_     )     )
			]  # the reference grid
			a__     = 1
			a__     = [
			    [0 for col in range(len(grid[0]     )     )] for row in range(len(SCREAMING_SNAKE_CASE_     )     )
			]  # the action grid

			a__     = init[0]
			a__     = init[1]
			a__     = 0
			a__     = g + heuristic[x][y]  # cost from starting cell to destination cell
			a__     = [[f, g, x, y]]

			a__     = False  # flag that is set when search is complete
			a__     = False  # flag set if we can't find expand

			while not found and not resign:
						if len(SCREAMING_SNAKE_CASE_     ) == 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()
									a__     = cell.pop()
									a__     = next_cell[2]
									a__     = next_cell[3]
									a__     = next_cell[1]

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

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


if __name__ == "__main__":
		lowerCAmelCase_   :   Tuple       =					[
		    [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],
		]

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

		# the cost map which pushes the path closer to the goal
		lowerCAmelCase_   :   Any       =					[[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])):
						lowerCAmelCase_   :   Union[str, Any]       =					abs(i - goal[0]) + abs(j - goal[1])
						if grid[i][j] == 1:
								# added extra penalty in the heuristic map
								lowerCAmelCase_   :   Union[str, Any]       =					99

		lowerCAmelCase_     ,      lowerCAmelCase_   :   Tuple       =					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])










'''simple docstring'''


class       UpperCamelCase__  :







	def __init__(				self			:   str , lowerCamelCase			:   int , lowerCamelCase			:   List[str]=None , lowerCamelCase			:   int=None		):




				'''simple docstring'''
				a__     = data
				a__     = previous
				a__     = next_node







	def __str__(				self			:   List[Any]		):




				'''simple docstring'''
				return F'''{self.data}'''







	def 						__a   (				self			:   List[Any]		):




				'''simple docstring'''
				return self.data







	def 						__a   (				self			:   Tuple		):




				'''simple docstring'''
				return self.next







	def 						__a   (				self			:   Union[str, Any]		):




				'''simple docstring'''
				return self.previous






class       UpperCamelCase__  :







	def __init__(				self			:   int , lowerCamelCase			:   Tuple		):




				'''simple docstring'''
				a__     = head







	def __iter__(				self			:   Any		):




				'''simple docstring'''
				return self







	def 						__a   (				self			:   List[Any]		):




				'''simple docstring'''
				if not self.current:
							raise StopIteration
				else:
							a__     = self.current.get_data()
							a__     = self.current.get_next()
							return value






class       UpperCamelCase__  :







	def __init__(				self			:   Tuple		):




				'''simple docstring'''
				a__     = None  # First node in list
				a__     = None  # Last node in list







	def __str__(				self			:   Any		):




				'''simple docstring'''
				a__     = self.head
				a__     = []
				while current is not None:
							nodes.append(current.get_data()		)
							a__     = current.get_next()
				return " ".join(str(lowerCamelCase		) for node in nodes		)







	def __contains__(				self			:   Optional[int] , lowerCamelCase			:   int		):




				'''simple docstring'''
				a__     = self.head
				while current:
							if current.get_data() == value:
										return True
							a__     = current.get_next()
				return False







	def __iter__(				self			:   int		):




				'''simple docstring'''
				return LinkedListIterator(self.head		)







	def 						__a   (				self			:   str		):




				'''simple docstring'''
				if self.head:
							return self.head.get_data()
				return None







	def 						__a   (				self			:   Union[str, Any]		):




				'''simple docstring'''
				if self.tail:
							return self.tail.get_data()
				return None







	def 						__a   (				self			:   List[Any] , lowerCamelCase			:   Node		):




				'''simple docstring'''
				if self.head is None:
							a__     = node
							a__     = node
				else:
							self.insert_before_node(self.head , lowerCamelCase		)







	def 						__a   (				self			:   List[str] , lowerCamelCase			:   Node		):




				'''simple docstring'''
				if self.head is None:
							self.set_head(lowerCamelCase		)
				else:
							self.insert_after_node(self.tail , lowerCamelCase		)







	def 						__a   (				self			:   List[str] , lowerCamelCase			:   int		):




				'''simple docstring'''
				a__     = Node(lowerCamelCase		)
				if self.head is None:
							self.set_head(lowerCamelCase		)
				else:
							self.set_tail(lowerCamelCase		)







	def 						__a   (				self			:   Any , lowerCamelCase			:   Node , lowerCamelCase			:   Node		):




				'''simple docstring'''
				a__     = node
				a__     = node.previous

				if node.get_previous() is None:
							a__     = node_to_insert
				else:
							a__     = node_to_insert

				a__     = node_to_insert







	def 						__a   (				self			:   Tuple , lowerCamelCase			:   Node , lowerCamelCase			:   Node		):




				'''simple docstring'''
				a__     = node
				a__     = node.next

				if node.get_next() is None:
							a__     = node_to_insert
				else:
							a__     = node_to_insert

				a__     = node_to_insert







	def 						__a   (				self			:   Union[str, Any] , lowerCamelCase			:   int , lowerCamelCase			:   int		):




				'''simple docstring'''
				a__     = 1
				a__     = Node(lowerCamelCase		)
				a__     = self.head
				while node:
							if current_position == position:
										self.insert_before_node(lowerCamelCase , lowerCamelCase		)
										return
							current_position += 1
							a__     = node.next
				self.insert_after_node(self.tail , lowerCamelCase		)







	def 						__a   (				self			:   List[Any] , lowerCamelCase			:   int		):




				'''simple docstring'''
				a__     = self.head
				while node:
							if node.get_data() == item:
										return node
							a__     = node.get_next()
				raise Exception("Node not found"		)







	def 						__a   (				self			:   List[Any] , lowerCamelCase			:   List[str]		):




				'''simple docstring'''
				if (node := self.get_node(lowerCamelCase		)) is not None:
							if node == self.head:
										a__     = self.head.get_next()

							if node == self.tail:
										a__     = self.tail.get_previous()

							self.remove_node_pointers(lowerCamelCase		)







	@staticmethod
	def 						__a   (				lowerCamelCase			:   Node		):




				'''simple docstring'''
				if node.get_next():
							a__     = node.previous

				if node.get_previous():
							a__     = node.next

				a__     = None
				a__     = None







	def 						__a   (				self			:   List[str]		):




				'''simple docstring'''
				return self.head is None







def    _lowerCamelCase  ()   ->    None:
			pass


if __name__ == "__main__":
		import doctest

		doctest.testmod()



