





"""simple docstring"""




from __future__ import annotations

import time

lowerCamelCase_     :						Union[str, Any]						=					list[tuple[int, int]]

lowerCamelCase_     :						Optional[Any]						=					[
    [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],
]

lowerCamelCase_     :						List[str]						=					[[-1, 0], [0, -1], [1, 0], [0, 1]]  # up, left, down, right

class  _UpperCAmelCase  :



      '''simple docstring'''

      def __init__(     self					,      snake_case_					,      snake_case_					,      snake_case_					,      snake_case_					,      snake_case_  ):

        """simple docstring"""

        A_  :       Dict										=  pos_x
        A_  :       int										=  pos_y
        A_  :       List[Any]										=  (pos_y, pos_x)
        A_  :       List[str]										=  goal_x
        A_  :       Tuple										=  goal_y
        A_  :       List[str]										=  parent


class  _UpperCAmelCase  :



      '''simple docstring'''

      def __init__(     self					,      snake_case_					,      snake_case_  ):

        """simple docstring"""

        A_  :       Optional[int]										=  Node(start[1]					,      start[0]					,      goal[1]					,      goal[0]					,      snake_case_  )
        A_  :       int										=  Node(goal[1]					,      goal[0]					,      goal[1]					,      goal[0]					,      snake_case_  )

        A_  :       int										=  [self.start]
        A_  :       Dict										=  False

      def 					lowerCamelCase_			(     self  ):

        """simple docstring"""

        while self.node_queue:
          A_  :       List[Any]										=  self.node_queue.pop(0  )

          if current_node.pos == self.target.pos:
            A_  :       Optional[Any]										=  True
            return self.retrace_path(snake_case_  )

          A_  :       str										=  self.get_successors(snake_case_  )

          for node in successors:
            self.node_queue.append(snake_case_  )

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

      def 					lowerCamelCase_			(     self					,      snake_case_  ):

        """simple docstring"""

        A_  :       Optional[int]										=  []
        for action in delta:
          A_  :       Any										=  parent.pos_x + action[1]
          A_  :       Optional[Any]										=  parent.pos_y + action[0]
          if not (0 <= pos_x <= len(grid[0]  ) - 1 and 0 <= pos_y <= len(snake_case_  ) - 1):
            continue

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

          successors.append(
              Node(snake_case_					,      snake_case_					,      self.target.pos_y					,      self.target.pos_x					,      snake_case_  )  )
        return successors

      def 					lowerCamelCase_			(     self					,      snake_case_  ):

        """simple docstring"""

        A_  :       Any										=  node
        A_  :       List[Any]										=  []
        while current_node is not None:
          path.append((current_node.pos_y, current_node.pos_x)  )
          A_  :       Dict										=  current_node.parent
        path.reverse()
        return path


class  _UpperCAmelCase  :



      '''simple docstring'''

      def __init__(     self					,      snake_case_					,      snake_case_  ):

        """simple docstring"""

        A_  :       Any										=  BreadthFirstSearch(snake_case_					,      snake_case_  )
        A_  :       Optional[Any]										=  BreadthFirstSearch(snake_case_					,      snake_case_  )
        A_  :       Tuple										=  False

      def 					lowerCamelCase_			(     self  ):

        """simple docstring"""

        while self.fwd_bfs.node_queue or self.bwd_bfs.node_queue:
          A_  :       Dict										=  self.fwd_bfs.node_queue.pop(0  )
          A_  :       Any										=  self.bwd_bfs.node_queue.pop(0  )

          if current_bwd_node.pos == current_fwd_node.pos:
            A_  :       List[str]										=  True
            return self.retrace_bidirectional_path(
                snake_case_					,      snake_case_  )

          A_  :       Tuple										=  current_bwd_node
          A_  :       List[Any]										=  current_fwd_node

          A_  :       List[Any]										=  {
              self.fwd_bfs: self.fwd_bfs.get_successors(snake_case_  ),
              self.bwd_bfs: self.bwd_bfs.get_successors(snake_case_  ),
          }

          for bfs in [self.fwd_bfs, self.bwd_bfs]:
            for node in successors[bfs]:
              bfs.node_queue.append(snake_case_  )

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

      def 					lowerCamelCase_			(     self					,      snake_case_					,      snake_case_  ):

        """simple docstring"""

        A_  :       Optional[int]										=  self.fwd_bfs.retrace_path(snake_case_  )
        A_  :       Union[str, Any]										=  self.bwd_bfs.retrace_path(snake_case_  )
        bwd_path.pop()
        bwd_path.reverse()
        A_  :       int										=  fwd_path + bwd_path
        return path


if __name__ == "__main__":
   # all coordinates are given in format [y,x]
   import doctest

   doctest.testmod()
   lowerCamelCase_     :						Any						=					(0, 0)
   lowerCamelCase_     :						str						=					(len(grid) - 1, len(grid[0]) - 1)
   for elem in grid:
      print(elem)

   lowerCamelCase_     :						List[str]						=					time.time()
   lowerCamelCase_     :						Tuple						=					BreadthFirstSearch(init, goal)
   lowerCamelCase_     :						int						=					bfs.search()
   lowerCamelCase_     :						List[Any]						=					time.time() - start_bfs_time

   print('Unidirectional BFS computation time : ', bfs_time)

   lowerCamelCase_     :						Optional[Any]						=					time.time()
   lowerCamelCase_     :						List[str]						=					BidirectionalBreadthFirstSearch(init, goal)
   lowerCamelCase_     :						Dict						=					bd_bfs.search()
   lowerCamelCase_     :						Union[str, Any]						=					time.time() - start_bd_bfs_time

   print('Bidirectional BFS computation time : ', bd_bfs_time)






"""simple docstring"""




from heapq import heappop, heappush

import numpy as np





def 						UpperCAmelCase__		(     _UpperCAmelCase ,					_UpperCAmelCase ,					_UpperCAmelCase ,					_UpperCAmelCase ,					):






  """simple docstring"""





  A_						,       A_  :       List[str]										=  grid.shape
  A_  :       Optional[int]										=  [-1, 1, 0, 0]
  A_  :       str										=  [0, 0, -1, 1]
  if allow_diagonal:
    dx += [-1, -1, 1, 1]
    dy += [-1, 1, -1, 1]

  A_						,       A_  :       List[Any]										=  [(0, source)], set()
  A_  :       Optional[Any]										=  np.full((rows, cols) ,					np.inf					)
  A_  :       int										=  0
  A_  :       Optional[int]										=  np.empty((rows, cols) ,					dtype=_UpperCAmelCase					)
  A_  :       Optional[int]										=  None

  while queue:
    ((A_)						,       (A_))  :       str										=  heappop(_UpperCAmelCase					)
    if (x, y) in visited:
      continue
    visited.add((x, y)					)

    if (x, y) == destination:
      A_  :       int										=  []
      while (x, y) != source:
        path.append((x, y)					)
        A_						,       A_  :       List[Any]										=  predecessors[x, y]
      path.append(_UpperCAmelCase					)  # add the source manually
      path.reverse()
      return matrix[destination], path

    for i in range(len(_UpperCAmelCase					)					):
      A_						,       A_  :       Tuple										=  x + dx[i], y + dy[i]
      if 0 <= nx < rows and 0 <= ny < cols:
        A_  :       Union[str, Any]										=  grid[nx][ny]
        if next_node == 1 and matrix[nx, ny] > dist + 1:
          heappush(_UpperCAmelCase ,					(dist + 1, (nx, ny))					)
          A_  :       Optional[Any]										=  dist + 1
          A_  :       Optional[Any]										=  (x, y)

  return np.inf, []


if __name__ == "__main__":
   import doctest

   doctest.testmod()