
from __future__ import annotations

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

def 				SCREAMING_SNAKE_CASE     (      __UpperCamelCase :						list[list[int]]							,						__UpperCamelCase :						list[int]							,						__UpperCamelCase :						list[int]							,						__UpperCamelCase :						int							,						__UpperCamelCase :						list[list[int]]							,						) ->       tuple[list[list[int]], list[list[int]]]:

						"""simple docstring"""







						A__  :	Any         =							[
						    [0 for col in range(len(grid[0]       )       )] for row in range(len(a_       )       )
						]  # the reference grid
						A__  :	Optional[Any]         =							1
						A__  :	Dict         =							[
						    [0 for col in range(len(grid[0]       )       )] for row in range(len(a_       )       )
						]  # the action grid

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

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

						while not found and not resign:
												if len(a_       ) == 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__  :	List[str]         =							cell.pop()
																		A__  :	Optional[int]         =							next_cell[2]
																		A__  :	int         =							next_cell[3]
																		A__  :	Union[str, Any]         =							next_cell[1]

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

						A__  :	Optional[Any]         =							[]
						for i in range(len(a_       )       ):
												path.append(invpath[len(a_       ) - 1 - i]       )
						return path, action


if __name__ == "__main__":
					_SCREAMING_SNAKE_CASE    :      Optional[Any]          =			[
					    [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],
					]

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

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

					_SCREAMING_SNAKE_CASE   ,     _SCREAMING_SNAKE_CASE    :      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])

import numpy as np

_SCREAMING_SNAKE_CASE    :      Any          =			[
    ['a', 'b', 'c', 'd', 'e'],
    ['f', 'g', 'h', 'i', 'k'],
    ['l', 'm', 'n', 'o', 'p'],
    ['q', 'r', 's', 't', 'u'],
    ['v', 'w', 'x', 'y', 'z'],
]







class  UpperCamelCase__		:







	'''simple docstring'''





	def __init__(			self		):
					A__  :	List[Any]         =							np.array(UpperCamelCase__		)





	def   __snake_case				(			self				,       UpperCamelCase__		):
					A__       ,							A__  :	Any         =							np.where(letter == self.SQUARE		)
					A__  :	int         =							np.concatenate([indexa + 1, indexa + 1]		)
					return indexes





	def   __snake_case				(			self				,       UpperCamelCase__				,       UpperCamelCase__		):
					A__  :	Union[str, Any]         =							self.SQUARE[indexa - 1, indexa - 1]
					return letter





	def   __snake_case				(			self				,       UpperCamelCase__		):
					A__  :	List[str]         =							message.lower()
					A__  :	str         =							message.replace(''' '''				,       ''''''		)
					A__  :	Union[str, Any]         =							message.replace('''j'''				,       '''i'''		)

					A__  :	List[Any]         =							np.empty((2, len(UpperCamelCase__		))		)
					for letter_index in range(len(UpperCamelCase__		)		):
									A__  :	Any         =							self.letter_to_numbers(message[letter_index]		)

									A__  :	Optional[Any]         =							numbers[0]
									A__  :	List[str]         =							numbers[1]

					A__  :	List[str]         =							first_step.reshape(2 * len(UpperCamelCase__		)		)
					A__  :	List[Any]         =							''''''
					for numbers_index in range(len(UpperCamelCase__		)		):
									A__  :	Dict         =							int(second_step[numbers_index * 2]		)
									A__  :	List[str]         =							int(second_step[(numbers_index * 2) + 1]		)
									A__  :	Dict         =							self.numbers_to_letter(UpperCamelCase__				,       UpperCamelCase__		)
									A__  :	Tuple         =							encoded_message + letter

					return encoded_message





	def   __snake_case				(			self				,       UpperCamelCase__		):
					A__  :	str         =							message.lower()
					message.replace(''' '''				,       ''''''		)
					A__  :	List[Any]         =							np.empty(2 * len(UpperCamelCase__		)		)
					for letter_index in range(len(UpperCamelCase__		)		):
									A__  :	List[str]         =							self.letter_to_numbers(message[letter_index]		)
									A__  :	Dict         =							numbers[0]
									A__  :	int         =							numbers[1]

					A__  :	Optional[Any]         =							first_step.reshape((2, len(UpperCamelCase__		))		)
					A__  :	int         =							''''''
					for numbers_index in range(len(UpperCamelCase__		)		):
									A__  :	Tuple         =							int(second_step[0, numbers_index]		)
									A__  :	Dict         =							int(second_step[1, numbers_index]		)
									A__  :	List[str]         =							self.numbers_to_letter(UpperCamelCase__				,       UpperCamelCase__		)
									A__  :	Tuple         =							decoded_message + letter

					return decoded_message