





'''simple docstring'''






from __future__ import annotations

A__							:  Any    =list[tuple[int, int]]

A__							:  Dict    =[
    [0, 0, 0, 0, 0, 0, 0],
    [0, 1, 0, 0, 0, 0, 0],  # 0 are free path whereas 1's are obstacles
    [0, 0, 0, 0, 0, 0, 0],
    [0, 0, 1, 0, 0, 0, 0],
    [1, 0, 1, 0, 0, 0, 0],
    [0, 0, 0, 0, 0, 0, 0],
    [0, 0, 0, 0, 1, 0, 0],
]

A__							:  Tuple    =([-1, 0], [0, -1], [1, 0], [0, 1])  # up, left, down, right




class 					UpperCAmelCase	:




      def __init__(     self     :					List[Any]     ,     __snake_case     :					int     ,     __snake_case     :					int     ,     __snake_case     :					int     ,     __snake_case     :					int     ,     __snake_case     :					float     ,     __snake_case     :					Node | None     ,     )							-> Optional[Any]:
            _lowerCAmelCase					=				pos_x
            _lowerCAmelCase					=				pos_y
            _lowerCAmelCase					=				(pos_y, pos_x)
            _lowerCAmelCase					=				goal_x
            _lowerCAmelCase					=				goal_y
            _lowerCAmelCase					=				g_cost
            _lowerCAmelCase					=				parent
            _lowerCAmelCase					=				self.calculate_heuristic()




      def 							lowercase__       (     self     :					int    )							-> Dict:
            _lowerCAmelCase					=				abs(self.pos_x - self.goal_x    )
            _lowerCAmelCase					=				abs(self.pos_y - self.goal_y    )
            return dx + dy




      def __lt__(     self     :					Union[str, Any]     ,     __snake_case     :					int    )							-> int:
            return self.f_cost < other.f_cost




class 					UpperCAmelCase	:




      def __init__(     self     :					str     ,     __snake_case     :					tuple[int, int]     ,     __snake_case     :					tuple[int, int]    )							-> Dict:
            _lowerCAmelCase					=				Node(start[1]     ,     start[0]     ,     goal[1]     ,     goal[0]     ,     0     ,     lowerCamelCase__    )
            _lowerCAmelCase					=				Node(goal[1]     ,     goal[0]     ,     goal[1]     ,     goal[0]     ,     9_99_99     ,     lowerCamelCase__    )

            _lowerCAmelCase					=				[self.start]
            _lowerCAmelCase					=				[]

            _lowerCAmelCase					=				False




      def 							lowercase__       (     self     :					str    )							-> Dict:
            while self.open_nodes:
                  # Open Nodes are sorted using __lt__
                  self.open_nodes.sort()
                  _lowerCAmelCase					=				self.open_nodes.pop(0    )

                  if current_node.pos == self.target.pos:
                        _lowerCAmelCase					=				True
                        return self.retrace_path(lowerCamelCase__    )

                  self.closed_nodes.append(lowerCamelCase__    )
                  _lowerCAmelCase					=				self.get_successors(lowerCamelCase__    )

                  for child_node in successors:
                        if child_node in self.closed_nodes:
                              continue

                        if child_node not in self.open_nodes:
                              self.open_nodes.append(lowerCamelCase__    )
                        else:
                              # retrieve the best current path
                              _lowerCAmelCase					=				self.open_nodes.pop(self.open_nodes.index(lowerCamelCase__    )    )

                              if child_node.g_cost < better_node.g_cost:
                                    self.open_nodes.append(lowerCamelCase__    )
                              else:
                                    self.open_nodes.append(lowerCamelCase__    )

            if not self.reached:
                  return [self.start.pos]
            return None




      def 							lowercase__       (     self     :					List[Any]     ,     __snake_case     :					Node    )							-> str:
            _lowerCAmelCase					=				[]
            for action in delta:
                  _lowerCAmelCase					=				parent.pos_x + action[1]
                  _lowerCAmelCase					=				parent.pos_y + action[0]

                  if not (0 <= pos_x <= len(grid[0]    ) - 1 and 0 <= pos_y <= len(lowerCamelCase__    ) - 1):
                        continue

                  if grid[pos_y][pos_x] != 0:
                        continue

                  successors.append(
                      Node(
                          lowerCamelCase__     ,     lowerCamelCase__     ,     self.target.pos_y     ,     self.target.pos_x     ,     parent.g_cost + 1     ,     lowerCamelCase__     ,     )    )
            return successors




      def 							lowercase__       (     self     :					Dict     ,     __snake_case     :					Node | None    )							-> Tuple:
            _lowerCAmelCase					=				node
            _lowerCAmelCase					=				[]
            while current_node is not None:
                  path.append((current_node.pos_y, current_node.pos_x)    )
                  _lowerCAmelCase					=				current_node.parent
            path.reverse()
            return path


if __name__ == "__main__":
      A__							:  Any    =(0, 0)
      A__							:  str    =(len(grid) - 1, len(grid[0]) - 1)
      for elem in grid:
            print(elem)

      print('''------''')

      A__							:  List[str]    =GreedyBestFirst(init, goal)
      A__							:  Optional[int]    =greedy_bf.search()
      if path:
            for pos_x, pos_y in path:
                  A__							:  Optional[Any]    =2

            for elem in grid:
                  print(elem)











'''simple docstring'''
from collections.abc import Iterator, MutableMapping
from dataclasses import dataclass
from typing import Generic, TypeVar

snake_case_					:      Optional[Any]    			=    TypeVar('KEY')
snake_case_					:      Dict    			=    TypeVar('VAL')






@dataclass(frozen=lowercase		,   slots=lowercase  )
class 				lowercase__      (				Generic[KEY, VAL]  ):
	lowercase__    							=     42
	lowercase__    							=     42






class 				lowercase__      (				_Item  ):





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







							'''simple docstring'''
							super().__init__(lowerCamelCase__					,lowerCamelCase__					)





	def __bool__(					self   :							Tuple					):







							'''simple docstring'''
							return False
snake_case_					:      int    			=    _DeletedItem()






class 				lowercase__      (				MutableMapping[KEY, VAL]  ):





	def __init__(					self   :							Any					,lowerCamelCase__   :							int = 8					,lowerCamelCase__   :							float = 0.7_5					):







							'''simple docstring'''
							_UpperCamelCase   :						Union[str, Any]												=  initial_block_size
							_UpperCamelCase   :						list[_Item | None]												=  [None] * initial_block_size
							assert 0.0 < capacity_factor < 1.0
							_UpperCamelCase   :						Optional[int]												=  capacity_factor
							_UpperCamelCase   :						List[Any]												=  0





	def       UpperCamelCase_    (					self   :							Optional[int]					,lowerCamelCase__   :							KEY					):







							'''simple docstring'''
							return hash(lowerCamelCase__					) % len(self._buckets					)





	def       UpperCamelCase_    (					self   :							List[Any]					,lowerCamelCase__   :							int					):







							'''simple docstring'''
							return (ind + 1) % len(self._buckets					)





	def       UpperCamelCase_    (					self   :							Union[str, Any]					,lowerCamelCase__   :							int					,lowerCamelCase__   :							KEY					,lowerCamelCase__   :							VAL					):







							'''simple docstring'''
							_UpperCamelCase   :						str												=  self._buckets[ind]
							if not stored:
													_UpperCamelCase   :						str												=  _Item(lowerCamelCase__					,lowerCamelCase__					)
													self._len += 1
													return True
							elif stored.key == key:
													_UpperCamelCase   :						Union[str, Any]												=  _Item(lowerCamelCase__					,lowerCamelCase__					)
													return True
							else:
													return False





	def       UpperCamelCase_    (					self   :							Optional[int]					):







							'''simple docstring'''
							_UpperCamelCase   :						Dict												=  len(self._buckets					) * self._capacity_factor
							return len(self					) >= int(lowerCamelCase__					)





	def       UpperCamelCase_    (					self   :							Dict					):







							'''simple docstring'''
							if len(self._buckets					) <= self._initial_block_size:
													return False
							_UpperCamelCase   :						str												=  len(self._buckets					) * self._capacity_factor / 2
							return len(self					) < limit





	def       UpperCamelCase_    (					self   :							int					,lowerCamelCase__   :							int					):







							'''simple docstring'''
							_UpperCamelCase   :						int												=  self._buckets
							_UpperCamelCase   :						Dict												=  [None] * new_size
							_UpperCamelCase   :						str												=  0
							for item in old_buckets:
													if item:
																			self._add_item(item.key					,item.val					)





	def       UpperCamelCase_    (					self   :							int					):







							'''simple docstring'''
							self._resize(len(self._buckets					) * 2					)





	def       UpperCamelCase_    (					self   :							List[str]					):







							'''simple docstring'''
							self._resize(len(self._buckets					) // 2					)





	def       UpperCamelCase_    (					self   :							Union[str, Any]					,lowerCamelCase__   :							KEY					):







							'''simple docstring'''
							_UpperCamelCase   :						List[str]												=  self._get_bucket_index(lowerCamelCase__					)
							for _ in range(len(self._buckets					)					):
													yield ind
													_UpperCamelCase   :						Optional[int]												=  self._get_next_ind(lowerCamelCase__					)





	def       UpperCamelCase_    (					self   :							str					,lowerCamelCase__   :							KEY					,lowerCamelCase__   :							VAL					):







							'''simple docstring'''
							for ind in self._iterate_buckets(lowerCamelCase__					):
													if self._try_set(lowerCamelCase__					,lowerCamelCase__					,lowerCamelCase__					):
																			break





	def __setitem__(					self   :							Dict					,lowerCamelCase__   :							KEY					,lowerCamelCase__   :							VAL					):







							'''simple docstring'''
							if self._is_full():
													self._size_up()

							self._add_item(lowerCamelCase__					,lowerCamelCase__					)





	def __delitem__(					self   :							Optional[Any]					,lowerCamelCase__   :							KEY					):







							'''simple docstring'''
							for ind in self._iterate_buckets(lowerCamelCase__					):
													_UpperCamelCase   :						Any												=  self._buckets[ind]
													if item is None:
																			raise KeyError(lowerCamelCase__					)
													if item is _deleted:
																			continue
													if item.key == key:
																			_UpperCamelCase   :						Optional[Any]												=  _deleted
																			self._len -= 1
																			break
							if self._is_sparse():
													self._size_down()





	def __getitem__(					self   :							Dict					,lowerCamelCase__   :							KEY					):







							'''simple docstring'''
							for ind in self._iterate_buckets(lowerCamelCase__					):
													_UpperCamelCase   :						Any												=  self._buckets[ind]
													if item is None:
																			break
													if item is _deleted:
																			continue
													if item.key == key:
																			return item.val
							raise KeyError(lowerCamelCase__					)





	def __len__(					self   :							Dict					):







							'''simple docstring'''
							return self._len





	def __iter__(					self   :							List[str]					):







							'''simple docstring'''
							yield from (item.key for item in self._buckets if item)





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







							'''simple docstring'''
							_UpperCamelCase   :						Tuple												=  ' ,'.join(
							    F'{item.key}: {item.val}' for item in self._buckets if item					)
							return F'HashMap({val_string})'


