
from __future__ import annotations

import time

_snake_case      = list[tuple[int, int]]

_snake_case      = [
    [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],
]

_snake_case      = [[-1, 0], [0, -1], [1, 0], [0, 1]]  # up, left, down, right
class       _lowerCAmelCase  :

 """simple docstring"""

 def __init__(						self			:			Any					, SCREAMING_SNAKE_CASE__			:			List[str]					, SCREAMING_SNAKE_CASE__			:			List[Any]					, SCREAMING_SNAKE_CASE__			:			Tuple					, SCREAMING_SNAKE_CASE__			:			List[Any]					, SCREAMING_SNAKE_CASE__			:			Dict   ):






      """simple docstring"""



      UpperCamelCase						    =					pos_x
      UpperCamelCase						    =					pos_y
      UpperCamelCase						    =					(pos_y, pos_x)
      UpperCamelCase						    =					goal_x
      UpperCamelCase						    =					goal_y
      UpperCamelCase						    =					parent




class       _lowerCAmelCase  :

 """simple docstring"""

 def __init__(						self			:			Dict					, SCREAMING_SNAKE_CASE__			:			Any					, SCREAMING_SNAKE_CASE__			:			Tuple   ):






      """simple docstring"""



      UpperCamelCase						    =					Node(start[1]					, start[0]					, goal[1]					, goal[0]					, _lowerCamelCase   )
      UpperCamelCase						    =					Node(goal[1]					, goal[0]					, goal[1]					, goal[0]					, _lowerCamelCase   )

      UpperCamelCase						    =					[self.start]
      UpperCamelCase						    =					False

 def      __lowerCAmelCase  (						self			:			Optional[int]   ):






      """simple docstring"""



      while self.node_queue:
           UpperCamelCase						    =					self.node_queue.pop(0   )

           if current_node.pos == self.target.pos:
                UpperCamelCase						    =					True
                return self.retrace_path(_lowerCamelCase   )

           UpperCamelCase						    =					self.get_successors(_lowerCamelCase   )

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

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

 def      __lowerCAmelCase  (						self			:			Tuple					, SCREAMING_SNAKE_CASE__			:			Optional[int]   ):






      """simple docstring"""



      UpperCamelCase						    =					[]
      for action in delta:
           UpperCamelCase						    =					parent.pos_x + action[1]
           UpperCamelCase						    =					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					, _lowerCamelCase   )   )
      return successors






 def      __lowerCAmelCase  (						self			:			Optional[Any]					, SCREAMING_SNAKE_CASE__			:			Optional[Any]   ):






      """simple docstring"""



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




class       _lowerCAmelCase  :

 """simple docstring"""

 def __init__(						self			:			List[str]					, SCREAMING_SNAKE_CASE__			:			Any					, SCREAMING_SNAKE_CASE__			:			Any   ):






      """simple docstring"""



      UpperCamelCase						    =					BreadthFirstSearch(_lowerCamelCase					, _lowerCamelCase   )
      UpperCamelCase						    =					BreadthFirstSearch(_lowerCamelCase					, _lowerCamelCase   )
      UpperCamelCase						    =					False

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






      """simple docstring"""



      while self.fwd_bfs.node_queue or self.bwd_bfs.node_queue:
           UpperCamelCase						    =					self.fwd_bfs.node_queue.pop(0   )
           UpperCamelCase						    =					self.bwd_bfs.node_queue.pop(0   )

           if current_bwd_node.pos == current_fwd_node.pos:
                UpperCamelCase						    =					True
                return self.retrace_bidirectional_path(
                    _lowerCamelCase					, _lowerCamelCase   )

           UpperCamelCase						    =					current_bwd_node
           UpperCamelCase						    =					current_fwd_node

           UpperCamelCase						    =					{
               self.fwd_bfs: self.fwd_bfs.get_successors(_lowerCamelCase   ),
               self.bwd_bfs: self.bwd_bfs.get_successors(_lowerCamelCase   ),
           }

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

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






 def      __lowerCAmelCase  (						self			:			Union[str, Any]					, SCREAMING_SNAKE_CASE__			:			List[str]					, SCREAMING_SNAKE_CASE__			:			int   ):






      """simple docstring"""



      UpperCamelCase						    =					self.fwd_bfs.retrace_path(_lowerCamelCase   )
      UpperCamelCase						    =					self.bwd_bfs.retrace_path(_lowerCamelCase   )
      bwd_path.pop()
      bwd_path.reverse()
      UpperCamelCase						    =					fwd_path + bwd_path
      return path


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

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

 _snake_case      = time.time()
 _snake_case      = BreadthFirstSearch(init, goal)
 _snake_case      = bfs.search()
 _snake_case      = time.time() - start_bfs_time

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

 _snake_case      = time.time()
 _snake_case      = BidirectionalBreadthFirstSearch(init, goal)
 _snake_case      = bd_bfs.search()
 _snake_case      = time.time() - start_bd_bfs_time

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





"""simple docstring"""
def 					a__						(						)	-> Union[str, Any]:
      UpperCAmelCase__			:							Dict							=    []
      UpperCAmelCase__			:							Tuple							=    1

      while len(lowerCAmelCase    ) < 1E6:
            constant.append(str(lowerCAmelCase    )    )
            i += 1

      UpperCAmelCase__			:							Any							=    """""".join(lowerCAmelCase    )

      return (
          int(constant[0]    )
          * int(constant[9]    )
          * int(constant[99]    )
          * int(constant[9_99]    )
          * int(constant[99_99]    )
          * int(constant[9_99_99]    )
          * int(constant[99_99_99]    )
      )


if __name__ == "__main__":
    print(solution())

